1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
|
#include <iostream> #include <set> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int N = 100 + 5; int maze[N][N]; int dp[N][N]; int way[4][2] = {1, 0, 0, 1, -1, 0, 0, -1}; int n, m; struct { int x, y; }node[N]; bool check(int x,int y) { if(x>m||x<=0||y>m||y<=0) return 1; return 0; } int dfs(int x,int y) { Node now,next; now.x = x, now.y = y; if(dp[x][y]) return dp[x][y]; int ans = 0; for (int i = 1; i <= n;i++) { for (int j = 0; j < 4;j++) { next.x = now.x + i * way[j][0]; next.y = now.y + i * way[j][1]; if(check(next.x,next.y)) continue; if(maze[next.x][next.y]>maze[now.x][now.y]) ans = max(ans, dfs(next.x, next.y)); } } dp[x][y] = maze[x][y]+ans; return dp[x][y]; } int main() { while((cin>>m>>n)) { if(m==-1&&n==-1) return 0; memset(dp, 0, sizeof dp); for (int i = 1; i <= m;i++) { for (int j = 1; j <= m;j++) { scanf("%d", &maze[i][j]); } } cout << dfs(1,1) << endl; } }
|
近期评论