我爱崔老师系列之 POJ 1088 滑雪 DFS+记忆化搜索~

题目连接http://poj.org/problem?id=1088

这道题其实说实话知道了思路真的很简单，但是那天晚上做的时候很苦逼的错了好多地方然后查还没查出来= =。。。

表示DFS真的很吃力= =。。。

所谓的记忆化搜索现在看来就是吧上搜索过的给存起来。。。

需要一个状态方程

dp[i][j] = max(dp[i+1][j],dp[i-1][j],dp[i][j+1],dp[i][j-1]);

四个方向搜一遍找到最合适的即可。。。

代码

View Code

 1 #include <string.h>
 2 #include <stdio.h>
 3 int num[105][105];
 4 int map[105][105];
 5 int c,r;
 6 int dfs(int i,int j)
 7 {
 8     int max = 0;
 9     if(num[i][j])
10     return num[i][j];
11     if(i+1 <= r && map[i][j] > map[i+1][j])
12     {
13         if(!num[i+1][j])
14         num[i+1][j] = dfs(i+1,j);
15         if(max < num[i+1][j])
16         max = num[i+1][j];
17     }
18     if(i-1 > 0 && map[i][j] > map[i-1][j])
19     {
20         if(!num[i-1][j])
21         num[i-1][j] = dfs(i-1,j);
22         if(max < num[i-1][j])
23         max = num[i-1][j];
24     }
25     if(j+1 <= c && map[i][j] > map[i][j+1])
26     {
27         if(!num[i][j+1])
28         num[i][j+1] = dfs(i,j+1);
29         if(max < num[i][j+1])
30         max = num[i][j+1];
31     }
32     if(j-1 > 0 && map[i][j] > map[i][j-1])
33     {
34         if(!num[i][j-1])
35         num[i][j-1] = dfs(i,j-1);
36         if(max < num[i][j-1])
37         max = num[i][j-1];
38     }
39     return max+1;
40 }
41 int main()
42 {
43     int i,j,n;
44     scanf("%d %d",&r,&c);
45     for(i = 1;i <= r;i++)
46         for(j = 1;j <= c;j++)
47         scanf("%d",&map[i][j]);
48 
49     memset(num,0,sizeof(num));
50     for(i = 1;i <= r;i++)
51     {
52         for(j = 1;j <= c;j++)
53         num[i][j] = dfs(i,j);
54     }
55 
56     int max,ans;
57     max = num[1][1];
58     for(i =1;i <= r;i++)
59     {
60     for(j = 1;j <= c;j++)
61     {
62         if(max < num[i][j])
63         max = num[i][j];
64     }
65     }
66 
67     printf("%d\n",max);
68 
69 }