AOJ 2538 Stack Maze - mayoko’s diary

問題

H*W の迷路が与えられる。この迷路には小文字のアルファベットで表される宝石と, 大文字のアルファベットで表されるそれに対応する宝石を埋め込む穴がある(例えば 'a' とそれに対応する 'A' がある, という感じ)。

あなたは (0, 0) から (H-1, W-1) に (y, x) -> (y+1, x), (y, x) -> (y, x+1) という移動のみを許して進んでいきたい。また, この際になるべく多くの宝石を対応する穴に埋め込んでいきたい。最大でいくつの宝石を埋め込めるか。

解法

dp[y1][x1][y2][x2] = ((y1, x1) から (y2, x2) に移動するまでに最大でいくつの宝石を埋め込めるか) という区間 dp っぽいものを考えます。

遷移は

(y1, x1) を素通りする場合
- (y1, x1) から下 or 右に移動してその最大値を答えとする
(y1, x1) が宝石の場合
- それに対応する穴を y1 <= y <= y2, x1 <= x <= x2 の間で探す。で, dp[y1+dy][x1+dx][y-dy][x-dx] + dp[y][x][y2][x2] + 1 というようなものを考える。
- ただ abs(y-y1) + abs(x-x1) == 1 の場合, 上のような遷移だと「(y1+dy, x1+dx) から (y-dy, x-dx) には行けないのでスルー」となってしまうので, この場合だけは例外的に扱います。

とすれば良いです。事前に can[y1][x1][y2][x2] = ( (y1, x1) から (y2, x2) に移動可能か) というのを事前計算しておけば上記の dp は O(A) (A は迷路の中にある同じ種類の穴の最大の数) でできます。問題文によると A <= 10 なのでこれで十分高速に答えを得られます。

const int INF = 1e9;
const int MAX = 55;

string board[MAX];
int dp[MAX][MAX][MAX][MAX];
bool can[MAX][MAX][MAX][MAX];
vector<pii> pnts[33];
int H, W;

int dfs(int y1, int x1, int y2, int x2) {
	int& ret = dp[y1][x1][y2][x2];
	if (ret != -1) return ret;
	if (y1 == y2 && x1 == x2) return ret = 0;
	ret = -INF;
	char c = board[y1][x1];
	if (c == '#') return ret;
	// 今いる点はスルーする
	if (y1 + 1 <= y2 && board[y1 + 1][x1] != '#') {
		ret = max(ret, dfs(y1 + 1, x1, y2, x2));
	}
	if (x1 + 1 <= x2 && board[y1][x1 + 1] != '#') {
		ret = max(ret, dfs(y1, x1 + 1, y2, x2));
	}
	if ('a' <= c && c <= 'z') {
		// 今いる点を選んでみる
		int index = c - 'a';
		for (auto p : pnts[index]) {
			int ny = p.first, nx = p.second;
			if (ny > y2 || nx > x2) continue;
			if (abs(ny - y1) + abs(nx - x1) == 1) {
				ret = max(ret, 1 + dfs(ny, nx, y2, x2));
			}
			else {
				for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
					int ny1 = y1 + dy[i], nx1 = x1 + dx[i];
					if (ny1 > y2 || nx1 > x2) continue;
					int bny = ny - dy[j], bnx = nx - dx[j];
					if (bny < y1 || bnx < x1) continue;
					if (!can[ny1][nx1][bny][bnx]) continue;
					ret = max(ret, 1 + dfs(ny1, nx1, bny, bnx) + dfs(ny, nx, y2, x2));
				}
			}
		}
	}
	return ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (cin >> H >> W) {
		if (H == 0 && W == 0) break;
		for (int i = 0; i < H; i++)
			cin >> board[i];
		for (int i = 0; i < 30; i++)
			pnts[i].clear();
		for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
			char c = board[i][j];
			if ('A' <= c && c <= 'Z') {
				pnts[c - 'A'].emplace_back(i, j);
			}
		}
		memset(can, false, sizeof(can));
		for (int y = H - 1; y >= 0; y--) for (int x = W - 1; x >= 0; x--) {
			if (board[y][x] == '#') continue;
			can[y][x][y][x] = true;
			if (y + 1 < H && board[y + 1][x] != '#') {
				for (int y1 = y + 1; y1 < H; y1++) for (int x1 = x; x1 < W; x1++) {
					can[y][x][y1][x1] |= can[y + 1][x][y1][x1];
				}
			}
			if (x + 1 < W && board[y][x + 1] != '#') {
				for (int y1 = y; y1 < H; y1++) for (int x1 = x + 1; x1 < W; x1++) {
					can[y][x][y1][x1] |= can[y][x + 1][y1][x1];
				}
			}
		}
		memset(dp, -1, sizeof(dp));
		int ans = dfs(0, 0, H - 1, W - 1);
		if (ans < 0) ans = -1;
		cout << ans << endl;
	}
	return 0;
}

stack みたいな問題は順列っぽい -> 区間 dp？みたいな反射がある。