POJ1088 滑雪:http://poj.org/problem?id=1088
Tags: mDFS(记忆化搜索)
Code:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 110; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int h[maxn][maxn]; int dp[maxn][maxn]; int R, C; int DP(int x, int y) { int i, xx, yy; if(dp[x][y]!=-1) return dp[x][y]; int ans = 0; for(i=0; i<4; i++) { xx = x+dx[i]; yy = y+dy[i]; if(xx<0||xx>=R||yy<0||yy>=C||h[x][y]<=h[xx][yy]) continue; ans = max(ans, DP(xx,yy) ); } return dp[x][y] = ans + 1; } int main() { int i, j, ans, tmp; while(cin>>R>>C) { ans = 0; for(i=0; i<R; i++) for(j=0; j<C; j++) { cin>>h[i][j]; } memset(dp,-1,sizeof(dp)); for(i=0; i<R; i++) for(j=0; j<C; j++) { tmp = DP(i,j); ans = max(ans,tmp); } cout<<ans<<endl; } return 0; }