2012-2013 JOI予選 問6 : Gifts

問題文 : お土産購入計画

解法 :
上または左に3回しか戻れないということは, 7ターン以上前の状態に戻ることが不可能ということを指す.
そこで, 6ターン前までに移動した方向を, bitで管理して持つ(e.x: 00->右 01->下, 10->左, 11->上).

1つの方向を2bitで管理できるので, 6 * 2 = 12bitあればbitでの移動方向の管理が可能である.

この情報を元に, 純粋に再帰を行い, その過程をメモすれば良い.
メモする内容は, 「6ターン前までの移動方向」「今いる座標」「あと何回上か左に動けるか」があれば十分である.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int w, h, k;
int memo[1 << 12][4][50][50];
int mask;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
char field[64][64];

bool check(int ny, int nx)
{
	return (0 <= ny && ny < h && 0 <= nx && nx < w);
}

int getMax(int bit, int left, int ty, int tx)
{
	if (memo[bit][left][ty][tx] != -1) return (memo[bit][left][ty][tx]);
	
	if (ty == h - 1 && tx == w - 1 && left == 0){
		return (0);
	}
	
	int px = tx, py = ty;
	bool same = false;
	for (int i = 0; i < 2 * k; i++){
		px += -dx[(bit >> (2 * i)) & 3];
		py += -dy[(bit >> (2 * i)) & 3];
		if (px == tx && py == ty){
			same = true;
			break;
		}
	}
	
	int ret = 0;
	
	if (!same && field[ty][tx] != '.') ret += field[ty][tx] - '0';
	
	int val = -999999;
	for (int i = 0; i < 4; i++){
		if (left == 0 && i >= 2) break;
		int nx = tx + dx[i], ny = ty + dy[i];
		if (check(ny, nx) && field[ny][nx] != '#'){
			val = max(val, getMax(((bit << 2) | i) & mask, left - (i >= 2), ny, nx) + ret);
		}
	}
	
	return (memo[bit][left][ty][tx] = val);
}

int main()
{
	scanf("%d %d %d", &h, &w, &k);
	
	mask = (1 << (4 * k)) - 1;
	
	for (int i = 0; i < h; i++){
		scanf("%s", field[i]);
	}
	
	memset(memo, -1, sizeof(memo));
	
	int res = getMax(0, k, 0, 0);
	
	printf("%d\n", res < 0 ? 0 : res);
	
	return (0);
}

21
704
19
253
274