[題目描述]
有一個n*n的迷宮，每個方格里都有著相應的數字。你從左上角出發，每次可以向上下左右四個方向最多移動k格，并且要求你每次到達的方格里的數字必須大于上一次所在方格的數字。現在要求你走過的方格的所有數之和最大，問這個最大和是多少。
[輸入]
輸入數據第一行為兩個正整數N、K（1<=N<=100,0<=K<=N）
接下來的n行，每行有n個不超過integer范圍的整數，表示地圖中的數。
[輸出]
輸出數據只有一行，為最大的和。
[輸入輸出示例]
輸入(maze.in) 輸出(maze.out)
3 1 25
3 6 2
4 7 9
2 3 1
[評分標準]
對于每個測試數據，如果你能夠得出正確的答案，那么你將得到滿分，否則得0分。
[分析]
很明顯的動態規劃，應該是從《滑雪》那道題改編而來的。
1: #include <stdio.h>
2: #define maxn 110
3:
4: int a[maxn][maxn];
5: int f[maxn][maxn];
6: int n,ans,k;
7: int xx[4]={0,0,1,-1};
8: int yy[4]={1,-1,0,0};
9:
10: int find(int x,int y)
11: {
12: if (f[x][y]) return f[x][y];
13: int temx,temy;
14: for (int i=0;i<4;++i)
15: for (int j=1;j<=k;++j)
16: {
17: temx=x+xx[i]*j;
18: temy=y+yy[i]*j;
19: if ((temx>0)&&(temx<=n)&&(temy>0)&&(temy<=n))
20: if ((a[temx][temy]>a[x][y])&&(find(temx,temy)>f[x][y]))
21: f[x][y]=find(temx,temy);
22: }
23: f[x][y]+=a[x][y];
24: return f[x][y];
25: }
26:
27: int main()
28: {
29: freopen("maze.in","r",stdin);
30: freopen("maze.out","w",stdout);
31:
32: scanf("%d%d",&n,&k);
33: for (int i=1;i<=n;++i)
34: for (int j=1;j<=n;++j)
35: scanf("%d",&a[i][j]);
36: printf("%d\n",find(1,1));
37: return 0;
38: }
39: