TopCoder SRM 593 Div1 Easy HexagonalBoard

SRM593に参加。Easyは若干時間をかけたものの正解できたが、Mediumを正解できず微妙な順位。
レートは微増。
http://community.topcoder.com/stat?c=problem_statement&pm=12784

問題

六角座標で構成されたセル群のうち、いくつかが指定される。
指定されたセルは、互いに隣接するものは異なる色で塗らなければならない。
条件を満たす最少の色数を答えよ。

解法

四色問題が有名な塗り分け問題であるが、六角座標では以下のようにすれば3色で塗れる。
よって、上限は3色。後はそれ以下で塗れるかどうか調べればよい。

 ＢＣＡＢＣＡＢＣＡＢ
ＣＡＢＣＡＢＣＡＢＣ
 ＢＣＡＢＣＡＢＣＡＢ
ＣＡＢＣＡＢＣＡＢＣ
 ＢＣＡＢＣＡＢＣＡＢ
ＣＡＢＣＡＢＣＡＢＣ

指定マスが1個もなければ、塗る必要がないので0色。
指定マスが1個以上あるが、互いに隣接してなければ全部同じ色で塗れるので1色。

後は2色かどうかである。
最初は3つのセルが三角形を作る場合に3色か…と思ったら、それ以外でも3色の場合がある。
たとえば以下のループは長さが奇数なので、＊の部分が2色では塗れない。

 ＡＢＡ  ＢＡ
Ｂ    ＢＡ  Ｂ
 Ａ          Ａ
  ＢＡＢＡＢ＊
||>

よって、2色で塗れるかDFSで試して、塗れないなら3色と答えればよい。

>|cpp|
int dx[6]={1,-1,1,0,-1,0};
int dy[6]={0,0,-1,-1,1,1};
class HexagonalBoard {
	public:
	int N,C;
	vector <string> B;
	int col[51][51];
	int okok2() {
		int x,y,i,ty,tx;
		FOR(x,N) FOR(y,N) col[y][x]=-1;
		queue<int> Q;
		FOR(x,N) FOR(y,N) if(B[y][x]=='X' && col[y][x]==-1) {
			col[y][x]=0;
			Q.push(y*100+x);
			while(!Q.empty()) {
				int k=Q.front();
				int cy=k/100,cx=k%100;
				Q.pop();
				
				FOR(i,6) {
					int tx=cx+dx[i];
					int ty=cy+dy[i];
					if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
					if(B[ty][tx]!='X') continue;
					if(col[ty][tx]==col[cy][cx]) return 0;
					if(col[ty][tx]==-1) {
						col[ty][tx]=1-col[cy][cx];
						Q.push(ty*100+tx);
					}
				}
			}
		}
		return 1;
	}
	
	
	int minColors(vector <string> board) {
		int x,y,i;
		B=board;
		N=board.size();
		C=0;
		FOR(y,N) FOR(x,N) C+=B[y][x]=='X';
		if(C==0) return 0;
		int ng=0;
		FOR(y,N) FOR(x,N) if(B[y][x]=='X') {
			FOR(i,6) {
				int tx=x+dx[i];
				int ty=y+dy[i];
				if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
				if(B[ty][tx]=='X') ng=1;
			}
		}
		if(ng==0) return 1;
		
		if(okok2()) return 2;
		return 3;
	}
}

まとめ

DFSの量が多くなって結構時間がかかってしまった。
この問題、意外とSuccess Rateが低かったが、正解できてよかった。