題意：給出一個n*n網格，每個網格裡都有一個數字，一個人要從(1,1)走到(n,n)，要求隻能向左走或向右走或向下走，不能走重複的格子，且走過格子是負數的個數不超過k，問走到(n,n)走過格子最大和是多少，如果無法滿足條件輸出Impossible。
題解：f[r][c][cnt][d]表示走到第i,j個格子時已經走了cnt個負數格子，且面朝方向d(0：下 1：右 2：左)，遞歸找路徑就可以了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 80;
const long long INF = -1000000000000;
int n, k, vis[N][N][6][3];
long long f[N][N][6][3], res, g[N][N];
int flagx[3] = {1, 0, 0};
int flagy[3] = {0, 1, -1};
long long dp(int r, int c, int cnt, int d) {
if (cnt > k)
return INF;
if (r == n && c == n)
return g[r][c];
long long &cur = f[r][c][cnt][d];
if (vis[r][c][cnt][d])
return cur;
vis[r][c][cnt][d] = 1;
cur = INF;
for (int i = 0; i < 3; i++) {
int x = flagx[i] + r;
int y = flagy[i] + c;
if (x > n || x < 1 || y > n || y < 1)
continue;
if (d + i == 3) //原先是向左隻能向下或繼續向左，原先向右隻能向下或繼續向右，避免重複
continue;
long long flag = g[x][y] < 0 ? 1 : 0;
long long temp = dp(x, y, cnt + flag, i);
if (temp != INF)
cur = max(cur, temp + g[r][c]);
}
return cur;
}
int main() {
int cas = 1;
while (scanf("%d%d", &n, &k) && (n + k)) {
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%lld", &g[i][j]);
long long flag = g[1][1] < 0 ? 1 : 0;
res = dp(1, 1, flag, 0);
printf("Case %d: ", cas++);
if (res != INF)
printf("%lld\n", res);
else
printf("impossible\n");
}
return 0;
}