HDOJ1078 FatMouse and Cheese【动态规划】

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #define N 101
 5 int a[N][N],b[N][N];
 6 int n,k;
 7 int dp(int x,int y)
 8 {
 9     int maxn,i,tx,ty;
10     if(b[x][y]!=-1)
11         return b[x][y];
12     maxn=0;
13     for (i=1;i<=k;i++)
14     {
15         tx=x+i;
16         if(tx>=0 && tx<n && a[tx][y]>a[x][y])
17         {
18             if(b[tx][y]==-1)//没有求出max，就进行dp
19                 b[tx][y]=dp(tx,y);
20             if(b[tx][y]>maxn)
21                 maxn=b[tx][y];
22         }            
23         tx=x-i;
24         if(tx>=0 && tx<n && a[tx][y]>a[x][y])
25         {
26             if(b[tx][y]==-1)        
27                 b[tx][y]=dp(tx,y);
28             if(b[tx][y]>maxn)        
29                 maxn=b[tx][y];
30         }            
31         ty=y+i;
32         if(ty>=0&&ty<n&&a[x][ty]>a[x][y])
33         {
34             if(b[x][ty]==-1)        
35                 b[x][ty]=dp(x,ty);
36             if(b[x][ty]>maxn)        
37                 maxn=b[x][ty];
38         }            
39         ty=y-i;
40         if(ty>=0&&ty<n&&a[x][ty]>a[x][y])
41         {
42             if(b[x][ty]==-1)        
43                 b[x][ty]=dp(x,ty);
44             if(b[x][ty]>maxn)        
45                 maxn=b[x][ty];
46         }            
47     }
48     b[x][y]=maxn+a[x][y];
49     return b[x][y];
50 }
51 int main()
52 {
53     int i,j;
54     while (scanf("%d%d",&n,&k),~n||~k)
55     {
56         for (i=0;i<n;i++)
57             for (j=0;j<n;j++)
58             {
59                 scanf("%d",&a[i][j]);
60                 b[i][j]=-1;
61             }
62                 
63         printf("%d\n",dp(0,0));
64     }
65     return 0;
66 }