【HDOJ】1078 FatMouse and Cheese

这道题目是典型的DFS+记忆化搜索, DP思想。
符合：含重叠子问题，无后效性等特点。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 #define MAXN 105
 6 int dp[MAXN][MAXN];
 7 int a[MAXN][MAXN];
 8 int n, k;
 9 
10 int max(int a, int b) {
11     return a>b ? a:b;
12 }
13 
14 int dfs(int x, int y) {
15     int i, j;
16 
17     if (dp[x][y]) {
18         return dp[x][y];
19     }
20 
21     for (i=1; i<=k; ++i) {
22         if (x-i>=0 && a[x][y]<a[x-i][y])
23             dp[x][y] = max(dp[x][y], dfs(x-i, y));
24         if (x+i<n && a[x][y]<a[x+i][y])
25             dp[x][y] = max(dp[x][y], dfs(x+i, y));
26         if (y-i>=0 && a[x][y]<a[x][y-i])
27             dp[x][y] = max(dp[x][y], dfs(x, y-i));
28         if (y+i<n && a[x][y]<a[x][y+i])
29             dp[x][y] = max(dp[x][y], dfs(x, y+i));
30     }
31     dp[x][y] += a[x][y];
32     return dp[x][y];
33 }
34 
35 int main() {
36     int i, j;
37 #ifndef ONLINE_JUDGE
38     freopen("data.in", "r", stdin);
39 #endif
40 
41     while (scanf("%d %d", &n, &k)!=EOF && (n>0 && k>0)) {
42         for (i=0; i<n; ++i)
43             for (j=0; j<n; ++j)
44                 scanf("%d", &a[i][j]);
45         memset(dp, 0, sizeof(dp));
46         int ans = dfs(0, 0);
47         printf("%d
", ans);
48     }
49 
50     return 0;
51 }