HDU 1078 FatMouse and Cheese(记忆化搜索)
2013-07-31 16:06:31

```#include<cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
# define MAX 111
using namespace std;

int dirx[4] = {1,-1,0,0} ;
int diry[4] = {0,0,1,-1} ;
int n,k;
int map[MAX][MAX];
long long dp[MAX][MAX];
int vis[MAX][MAX];

bool inside(int x,int y) {
if(x < 0 || x >=n || y < 0 || y >= n) {
return false;
}
return true;
}

void init() {

memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
}

long long dfs(int x,int y) {
if(dp[x][y] != 0) return dp[x][y];
vis[x][y] = 1;

long long maxx = -1;
for(int i=0; i<4; i++) {
for(int j=1; j<=k; j++) {
int xx = x + dirx[i] * j;
int yy = y + diry[i] * j;
if(inside(xx,yy) && vis[xx][yy] == 0 && map[xx][yy] > map[x][y]) {
maxx = max(maxx,dfs(xx,yy));
vis[xx][yy] = 0;
}
}
}
if(maxx == -1) {
return dp[x][y] = map[x][y];
}
return dp[x][y] = maxx + map[x][y];
}

int main() {
int i,j;
while(cin >> n >> k) {
if(n == -1 && k == -1) {
break;
}
init();
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
scanf("%d",&map[i][j]);
}
}
cout << dfs(0,0) << endl;
}
return 0;
}
```