題目大意:老鼠從(0,0)出發,每次在同一個方向上最多前進k步,且每次到達的位置上的數字都要比上一個位置上的數字大,求老鼠經過的位置上的數字的和的最大值
#include<stdio.h> #include<string.h> #define max(a,b) a>b?a:b int n; int k;//前進的步數 int map[105][105]; int ans[105][105];//記憶化搜索,保存中間搜索結果 int search(int x,int y) { int dx,dy;//要去的下一個位置 int i,maxx = 0; if(ans[x][y] != -1) return ans[x][y];//已經搜索過,直接返回結果 for(i = 1 ; i <= k ; i ++)//向前走的步數 { dx = x - i;//向上 if(dx >= 0 && dx < n && map[dx][y] > map[x][y]) { ans[dx][y] = search(dx,y); maxx = max(maxx,ans[dx][y]); } dx = x + i;//向下 if(dx >= 0 && dx < n && map[dx][y] > map[x][y]) { ans[dx][y] = search(dx,y); maxx = max(maxx,ans[dx][y]); } dy = y - i;//向左 if(dy >= 0 && dy < n && map[x][dy] > map[x][y]) { ans[x][dy] = search(x,dy); maxx = max(maxx,ans[x][dy]); } dy = y + i;//向右 if(dy >= 0 && dy < n && map[x][dy] > map[x][y]) { ans[x][dy] = search(x,dy); maxx = max(maxx,ans[x][dy]); } } return maxx + map[x][y]; } int main() { int i,j; while(scanf("%d%d",&n,&k) && (n != -1 && k != -1)) { for(i = 0 ; i < n ; i ++) for(j = 0 ; j < n ; j ++) scanf("%d",&map[i][j]); memset(ans,-1,sizeof(ans)); printf("%d\n",search(0,0)); } return 0; }