poj 1088/nyoj 10 滑雪（記憶化搜尋/DP）

題目連結：poj1088  nyoj10

#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b?a:b)
int map[105][105];
int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int dp[105][105];
int n,m;
int dfs(int x,int y)
{
    if(dp[x][y] > 1) return dp[x][y];
    for(int i = 0 ; i < 4 ; i ++)
    {
        int dx = x + d[i][0];
        int dy = y + d[i][1];
        if(dx < 0 || dx >= n || dy < 0 || dy >= m) continue;
        if(map[dx][dy] < map[x][y])//下一個點比這個點小
         dp[x][y] = max(dp[x][y],dfs(dx,dy) + 1);
    }
    return dp[x][y];
}
int main()
{
    //freopen("in.txt","r",stdin);
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
        {
            scanf("%d",&map[i][j]);
            dp[i][j] = 1;
        }
        int ans = 0;
        for(i = 0 ; i < n ; i ++)
        for(j = 0 ; j < m ; j ++)
          ans = max(ans,dfs(i,j));
        printf("%d\n",ans);
    }
    return 0;
}