UVA 10913 Walking on a Grid(记忆化搜
发布时间： 2013-09-26 10:32:35 作者： rapoo
UVA 10913 Walking on a Grid(记忆化搜索)
4th IIUC Inter-University Programming Contest, 2005
IWalking on a GridYou can only move left, right or down.(#include <stdio.h>#include <string.h>const int MAXN = 80, INF = -200000000, d[3][2] = {{0, -1}, {0, 1}, {1, 0}};int n, k, num[MAXN][MAXN], vis[MAXN][MAXN], i, j, kkk, l;long long dp[MAXN][MAXN][10][5], ans;void dfs(int x, int y, int kk, long long sum) {int i;if (kk > k)return;if (x == n - 1 && y == n - 1) {if (ans < sum)ans = sum;return;}for (i = 0; i < 3; i ++) {int xx = x + d[i][0];int yy = y + d[i][1];if (xx >= 0 && xx < n && yy >= 0 && yy < n && vis[xx][yy] == 0) {vis[xx][yy] = 1;if (num[xx][yy] < 0 && dp[xx][yy][kk + 1][i] < sum + num[xx][yy]) {dp[xx][yy][kk + 1][i] = sum + num[xx][yy];dfs(xx, yy, kk + 1, sum + num[xx][yy]);}else if (num[xx][yy] >= 0 && dp[xx][yy][kk][i] < sum + num[xx][yy]) {dp[xx][yy][kk][i] = sum + num[xx][yy];dfs(xx, yy, kk, sum + num[xx][yy]);}vis[xx][yy] = 0;}}}int main() {int t = 1;while (~scanf("%d%d", &n, &k) && n || k) {ans = INF;for (i = 0; i < n; i ++)for (j = 0; j < n; j ++)for (kkk = 0; kkk < 6; kkk ++)for (l = 0; l < 4; l ++)dp[i][j][kkk][l] = INF;memset(vis, 0, sizeof(vis));vis[0][0] = 1;for (i = 0; i < n; i ++)for (j = 0; j < n; j ++)scanf("%d", &num[i][j]);if (num[0][0] < 0) {dfs(0, 0, 1, num[0][0]);}else {dfs(0, 0, 0, num[0][0]);}if (ans != INF)printf("Case %d: %lld\n", t ++, ans);elseprintf("Case %d: impossible\n", t ++);}return 0;}