TopCoder SRM 593 Div1 Easy HexagonalBoard

問題

Hex格子上の図形が与えられる。
隣り合う格子を必ず違う色で塗るとき、図形のすべての格子に色をつけるためには何色必要か求めよ。

制約条件

図形は50x50に収まる

方針

Hexすべてが図形のときでも、3色あれば塗れるので、答えは3以下。


図形が空の場合、非連結な場合で0, 1を場合分け。
残りの場合は、格子を頂点とし、隣接する格子同士を辺で結んだグラフが2-彩色可能かを見ればいい。


これは適当にDFSすれば求まる。

ソースコード

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

int color[51][51], sz, st[10000], h, w, one;
vector<string> b;

bool rec(int y, int x, int col){
	color[y][x] = col;
	st[sz++] = y * w + x;
	
	rep(d, 6){
		int ny = y + dy[d], nx = x + dx[d];
		if(ny < 0 || nx < 0 || ny >= h || nx >= w || b[ny][nx] != 'X') continue;
		one = 0;
		if(color[ny][nx]){
			if(color[ny][nx] == col) return 0;
			continue;
		}
		if(!rec(ny, nx, -col)) return 0;
	}
	return 1;
}

struct HexagonalBoard{
	int minColors(vector<string> b){
		::b = b;
		h = b.size(), w = b[0].size();
		one = 1;
		bool zero = 1;
		rep(i, h) rep(j, w) if(b[i][j] == 'X' && !color[i][j]){
			sz = 0;
			zero = 0;
			if(!rec(i, j, 1)){
				one = 0;
				while(sz) color[st[sz-1] / w][st[sz-1] % w] = 0, sz--;
				if(!rec(i, j, -1)) return 3;
			}
		}
		if(zero) return 0;
		if(one) return 1;
		return 2;
	}
};

なんかコード間違ってます。すみません。
(動作は正しいんですが)