[題目描述]
有一個(gè)n*n的迷宮，每個(gè)方格里都有著相應(yīng)的數(shù)字。你從左上角出發(fā)，每次可以向上下左右四個(gè)方向最多移動(dòng)k格，并且要求你每次到達(dá)的方格里的數(shù)字必須大于上一次所在方格的數(shù)字。現(xiàn)在要求你走過的方格的所有數(shù)之和最大，問這個(gè)最大和是多少。
[輸入]
輸入數(shù)據(jù)第一行為兩個(gè)正整數(shù)N、K（1<=N<=100,0<=K<=N）
接下來的n行，每行有n個(gè)不超過integer范圍的整數(shù)，表示地圖中的數(shù)。
[輸出]
輸出數(shù)據(jù)只有一行，為最大的和。
[輸入輸出示例]
輸入(maze.in) 輸出(maze.out)
3 1 25
3 6 2
4 7 9
2 3 1
[評(píng)分標(biāo)準(zhǔn)]
對(duì)于每個(gè)測(cè)試數(shù)據(jù)，如果你能夠得出正確的答案，那么你將得到滿分，否則得0分。
[分析]
很明顯的動(dòng)態(tài)規(guī)劃，應(yīng)該是從《滑雪》那道題改編而來的。
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: