JAG 2012 模擬地区予選E - Stack Maze

問題文 : Stack Maze

解法 :

dp[y1][x1][y2][x2] : 区間D : x ∈ [x1, x2], y ∈ [y1, y2] で宝石を置ける個数の最大値とすると,
マス(y1, x1) から(y2, x2)に到達可能であれば, D' : x ∈ (x1, x2], y ∈ [y1, y2] などの, Dより小さい区間の最大値からこの値を計算することが可能である.

各アルファベットは高々10文字しかなく, 抜ける方向も2 * 2 = 4 通りしか無いので, 時間計算量はO(2 * 4 * 10 * H * H * W * W) = O(H^2W^2) で, 間に合う.
前もっていけるマスを計算し忘れないように注意.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cctype>

using namespace std;

typedef pair<int, int> P;

int memo[64][64][64][64];
bool ok[64][64][64][64];
char str[64][64];
int W, H;

int dy[2] = {0, 1};
int dx[2] = {1, 0};

vector<P> hole[26];

bool okx(int x)
{
	return (0 <= x && x < W);
}

bool oky(int y)
{
	return (0 <= y && y < H);
}

int getMax(int y1, int x1, int y2, int x2)
{
	if (y1 > y2 || x1 > x2) return (0);
	if (!okx(x1) || !okx(x2) || !oky(y1) || !oky(y2) || !ok[y1][x1][y2][x2]) return (-99999);
	
	if (memo[y1][x1][y2][x2] >= 0) return (memo[y1][x1][y2][x2]);
	
	int res = 0;
	res = max(res, max(getMax(y1 + 1, x1, y2, x2), getMax(y1, x1 + 1, y2, x2)));
	
	if (islower(str[y1][x1])){
		int l = str[y1][x1] - 'a';
		for (int i = 0; i < hole[l].size(); i++){
			int ny = hole[l][i].first, nx = hole[l][i].second;
			if (!ok[y1][x1][ny][nx] || y1 > ny || ny > y2 || x1 > nx || nx > x2) continue;
			for (int d1 = 0; d1 < 2; d1++){
				for (int d2 = 0; d2 < 2; d2++){
					res = max(res, getMax(y1 + dy[d1], x1 + dx[d1], ny - dy[d2], nx - dx[d2]) + getMax(ny, nx, y2, x2) + 1);
				}
			}
		}
	}
	
	return (memo[y1][x1][y2][x2] = res);
}

int main()
{
	while (scanf("%d %d", &H, &W) && W){
		memset(memo, -1, sizeof(memo));
		memset(ok, 0, sizeof(ok));
		
		for (int i = 0; i < 26; i++) hole[i].clear();
		
		for (int i = 0; i < H; i++){
			scanf("%s", str[i]);
			for (int j = 0; j < W; j++){
				if (isupper(str[i][j])) hole[str[i][j] - 'A'].push_back(P(i, j));
			}
		}
		
		queue<pair<P, P> > q;
		
		for (int i = 0; i < H; i++){
			for (int j = 0; j < W; j++){
				if (str[i][j] != '#'){
					ok[i][j][i][j] = 1;
					q.push(make_pair(P(i, j), P(i, j)));
				}
			}
		}
		
		while (q.size()){
			pair<P, P> x = q.front(); q.pop();
			
			if (x.second.first + 1 < H && str[x.second.first + 1][x.second.second] != '#'){
				if (!ok[x.first.first][x.first.second][x.second.first + 1][x.second.second]++){
					q.push(make_pair(x.first, P(x.second.first + 1, x.second.second)));
				}
			}
			if (x.second.second + 1 < W && str[x.second.first][x.second.second + 1] != '#'){
				if (!ok[x.first.first][x.first.second][x.second.first][x.second.second + 1]++){
					q.push(make_pair(x.first, P(x.second.first, x.second.second + 1)));
				}
			}
		}
		
		printf("%d\n", getMax(0, 0, H - 1, W - 1) < 0 ? -1 : getMax(0, 0, H - 1, W - 1));
	}
	
	return (0);
}