保存下当前点能走的最大步长,当下次从其他点走到该点,则能够立即判定步长.
因为起点不一定, 以及 走一次不一定能走完所有位置.
但是,每次从最高点走,总是好的.能够走的更多.
每次选择没有走过的记忆化搜索.就OK了. 注意,a[i][j]可以取0, 所以dp应该初始化小于0
解题代码
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<iostream> #include<algorithm> using namespace std; #define MAX(a,b) (a)>(b)?(a):(b) const int N = 110; const int inf = 0x3fffffff; int a[N][N], dp[N][N]; int n, m, ans; int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} }; bool vis[N][N]; struct node { int x, y, h; bool operator < (node tmp) const { return h > tmp.h; } }p[10101]; bool legal( int x, int y ) { if( (x>=1)&&(x<=n)&&(y>=1)&&(y<=m) ) return true; return false; } int dfs(int x, int y ) { if( dp[x][y] != -1 ) return dp[x][y]; int Max = 0; for(int i = 0; i < 4; i++) { int tmp = 0, xx = x+dir[i][0], yy = y+dir[i][1]; if( legal(xx,yy) && (a[x][y] > a[xx][yy] ) ) tmp = dfs( xx, yy ); Max = MAX( Max, tmp ); } return (dp[x][y] = Max+1); } int main() { while( scanf("%d%d",&n,&m) != EOF) { int Max = -1, size = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); p[size].x = i; p[size].y = j; p[size++].h = a[i][j]; } sort( p, p+size ); ans = 0; memset( dp, 0xff , sizeof(dp)); for(int i = 0; i < size; i++) { int tmp = 0, x = p[i].x, y = p[i].y; if( (dp[x][y] == -1 ) &&( a[x][y] >\ 0) ) { tmp = dfs( x, y ); if( tmp > ans ) ans = tmp; } } /* for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) printf("%d ", dp[i][j] ); puts(""); }*/ printf("%d\n", ans ); } return 0; }