POJ 1088 滑雪 (记忆化搜索)

 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

#include <cstdio>
#include <algorithm>
using namespace std;
int const MAX = 105;
int map[MAX][MAX], r, c;
int dp[MAX][MAX];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int DFS(int i, int j)
{
    int tmp = 0;
    if(dp[i][j])
        return dp[i][j];
    for(int k = 0; k < 4; k++)
    {
        int x = i + dx[k];
        int y = j + dy[k];
        if(x < 0|| y < 0 || x >= r || y >= c || map[x][y] >= map[i][j])
            continue;
        tmp = max(tmp, DFS(x, y));
    }
    dp[i][j] = tmp + 1;
    return dp[i][j];
}

int main()
{
    int ans = 0;
    scanf("%d %d", &r, &c);
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            scanf("%d", &map[i][j]);
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            ans = max(ans, DFS(i, j));
    printf("%d\n", ans);
}