Codeforces 432(#246 Div2 only) E. Square Tiling

問題

hxwのグリッドの各マスをA-Zの文字いずれかで埋める。
隣り合う（辺を共有する）マスであって、同じ文字が書かれたタイルは繋がっているとする。
繋がったタイルの塊は必ず正方形をしていなければならない。

辞書順で最小の埋め方を求めよ。

制約条件

h, w≦100

方針

左上から順に埋める。
使えそうな文字のうち、辞書順で最小のものを見つける。
これが一個左隣のマスよりも大きかったら、一個左隣のマスの塊の正方形を1拡大したほうが得なので、それができないか確認してみる。
できるんだったら拡大する。そうでなければその辞書順最小のものを使えばよい。

ソースコード

const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1};
int h, w;
string ans[100];

inline bool ok(int y, int x, char c){
	rep(d, 4){
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
		if(ans[ny][nx] == c) return 0;
	}
	return 1;
}
inline bool ok2(int y, int x, char c){
	if(ans[y][x] != '.') return 0;
	for(int d = 1; d < 4; d++){
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
		if(ans[ny][nx] == c) return 0;
	}
	return 1;
}
inline bool ok3(int y, int x, char c){
	if(ans[y][x] != '.') return 0;
	rep(d, 4) if(d != 1){
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
		if(ans[ny][nx] == c) return 0;
	}
	return 1;
}

inline bool check(int y, int x){
	int Y = y, X = x;
	while(y && ans[y - 1][x] == ans[y][x]) y--;
	while(x && ans[y][x - 1] == ans[y][x]) x--;
	while(Y + 1 < h && ans[Y + 1][X] == ans[Y][X]) Y++;
	while(X + 1 < w && ans[Y][X + 1] == ans[Y][X]) X++;
	
	if(Y + 1 >= h || X + 1 >= w) return 0;
	
	int l = Y - y + 2;
	rep(i, l) if(!ok2(Y + 1, x + i, ans[y][x]) || !ok3(y + i, X + 1, ans[y][x])) return 0;
	return 1;
}
void extend(int y, int x){
	int Y = y, X = x;
	while(y && ans[y - 1][x] == ans[y][x]) y--;
	while(x && ans[y][x - 1] == ans[y][x]) x--;
	while(Y + 1 < h && ans[Y + 1][X] == ans[Y][X]) Y++;
	while(X + 1 < w && ans[Y][X + 1] == ans[Y][X]) X++;
	
	int l = Y - y + 2;
	rep(i, l) ans[Y + 1][x + i] = ans[y + i][X + 1] = ans[y][x];
}

int main(){
	cin >> h >> w;
	rep(i, h) ans[i] = string(w, '.');
	rep(i, h) rep(j, w) if(ans[i][j] == '.'){
		
		char p = j ? ans[i][j - 1] : 'Z', c = 'A';
		for(; c < p; c++){
			if(ok(i, j, c)) break;
		}
		if(c != p) ans[i][j] = c;
		else if(check(i, j - 1)) extend(i, j - 1);
		else for(c = p + 1; ; c++){
			if(ok(i, j, c)){
				ans[i][j] = c;
				break;
			}
		}
	}
	rep(i, h) cout << ans[i] << endl;
	
	return 0;
}