UVA - 10913Walking on a Grid(記憶化搜索）

UVA - 10913Walking on a Grid(記憶化搜索）

題目：Walking on a Grid

題目大意：給出N * N的矩陣，每個格子裡都有一個值，現在要求從（1，1）走到（n, n)，只能往下，左，右這三個方向走，並且要求最多只能取k個負數，求這樣的要求下能得到的走過格子的值之和最大。

解題思路：記憶化搜索，但是這裡要四維的，因為要記錄方向，為了防止走回頭的路，並且取了幾個負數也要記錄。然後就是dfs了。狀態轉移方程：dp【x】【y】【d】【k】 = dp【x + dir【i】【0】】【y + dir【i】【1】】【i】【k1] + G[x][y]; d代表從（x, y)出發走的方向。k：負數的個數（包括x，y這個格子走過的格子的負數總數），k1要根據G【x + dir【i】【0】】【y + dir【i】【1】】】來定，為正就還是等於k，為負就等於k + 1；

發現初始化真心要小心。

代碼：

#include 
#include 

typedef long long ll;

const int N = 80;
const int M = 3;
const ll INF = 0x3f3f3f3f3f; 
const int dir[M][2] = {{0, -1}, {1, 0}, {0, 1}};

int G[N][N];
ll dp[N][N][6][M];
int n, k;

ll Max (const ll a, const ll b) { return a > b ? a: b;}

void init () {

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			for (int l = 0; l <= k; l++)
				for (int m = 0; m < M; m++)
					dp[i][j][l][m] = -INF;

	if (G[0][0] < 0)//一開始的（0，0）位置的值如果是負數的話，那麼取負數的機會就被占用了一個。
		k--;
	for (int l = 0; l <= k; l++)
		for (int m = 0; m < M; m++)
			dp[n - 1][n - 1][l][m] = G[n - 1][n - 1];
}

ll DP (int x, int y, int d, int cnt) {

	int newx, newy;
	ll &ans = dp[x][y][cnt][d];
	if (ans != -INF)
		return ans;

	ll temp;
	if (d == 1) {//取下的話，那麼三個方向都是可以取的

		for (int i = 0; i < M; i++) {
	
			newx = x + dir[i][0];
			newy = y + dir[i][1];
			if (newx < 0 || newx >= n || newy < 0 || newy >= n)
				continue;

			if (G[newx][newy] < 0 && cnt == k)
				continue;
			if (G[newx][newy] < 0 && cnt < k) {
				temp = DP(newx, newy, 2 - i, cnt + 1); 
				if (temp != -INF - 1)
					ans = Max (ans, temp + G[x][y]); 
			}
			if (G[newx][newy] >= 0) {
				temp = DP (newx, newy, 2 - i, cnt);
				if (temp != -INF - 1)
					ans = Max (ans, temp + G[x][y]);
			}
		}
	} else {//取左/右的話下次就不要取右/左。

		for (int i = (d + 1) % M; i != d; i = (i + 1) % M) {

			newx = x + dir[i][0];
			newy = y + dir[i][1];
			if (newx < 0 || newx >= n || newy < 0 || newy >= n)
				continue;

			if (G[newx][newy] < 0 && cnt == k)
				continue;
			if (G[newx][newy] < 0 && cnt < k) {
				temp = DP(newx, newy, 2 - i, cnt + 1); 
				if (temp != -INF - 1)
					ans = Max (ans, temp + G[x][y]); 
			}
			if (G[newx][newy] >= 0) {
				temp = DP (newx, newy, 2 - i, cnt);
				if (temp != -INF - 1)//當這個位置可以到的時候才計算
					ans = Max (ans, temp + G[x][y]);
			}
		}
	}

	if (ans == -INF)//代表以目前的要求不能到達這個格子
		ans = -INF - 1;
	return ans;
}

int main () {

	int cas = 0;
	while (scanf ("%d%d", &n, &k), n || k) {

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				scanf ("%d", &G[i][j]);

		init ();

		ll ans; 
		ans = DP(0, 0, 1, 0);

		printf ("Case %d:", ++cas);
		if (ans == -INF - 1)
			printf (" impossible\n");
		else
			printf (" %lld\n", ans);		
	}
	return 0;
}