SRM587 Div2 Hard "ThreeColorabilityEasy"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12699
訳
H * Wのマス目がある。マスの列は上から下に向かって0からH-1と番号付けられ、列は左から右に向かって0からW-1と番号が付けられている。マスの四隅を"格子点"と呼ぶ。つまり、H * Wのマス目には、(H+1) * (W+1)のマス目がある。
それぞれのマスのそれぞれの辺は、白い線となっている。加えて、それぞれのマスの、2つの対角線のうち、1つだけ白い線が引かれている。2つの格子点は白い線で結ばれている場合、それは隣接していると言われる。
私たちは赤、緑、青の3つの色を使って格子点を全て塗りたい。ただし、1つだけ制約があり、それは隣り合う格子点には、同じ色を使ってはならない、というものである。
あなたには、W文字の文字列がH個ある String[] cellsが与えられる。cells[i][j]が'N'であれば、マス[i][j]は左上から右下に向かって白い線で対角線が引かれているし、'Z'であれば、右上から左下に向かって白い線で対角線が引かれている。
全ての格子点が3色のどれかで塗りつぶせるのであれば"Yes"を、できないようならば"No"を返せ。
制約
1 <= H, W <= 50
考えた事
どこかの2つの隣り合う格子点に対し、塗る色を決めてしまう。そうすると、格子点の中で、塗るべき色が一意に決まるところがでてくる。そうゆう格子点にどんどん色を塗っていき、全て塗りきったらセフセフ。隣り合う格子点が3色使っている格子点がでてきたらアウアウ。
事後
もっと簡潔にかけるらしく、ある格子点に着目したとき、その格子点が属している4つのマスで、'Z'が1つ、または3つであれば、アウアウ!(なんで!?)
ソースコード
int P[55][55]; class ThreeColorabilityEasy { public: string isColorable(vector <string> cells){ int R = cells.size() + 1; int W = cells[0].length() + 1; int S = R * W; memset( P, 0, sizeof(P) ); // とりあえず左上と、その右隣の格子点に色を塗る P[0][0] = 1; P[0][1] = 2; int cul = 2; // 塗られた格子点の数 while( cul < S ){ // 各格子点を調べる for( int y = 0; y < R; y++ ){ for( int x = 0; x < W; x++ ){ if( P[y][x] != 0 ) continue; // もう塗ってあった bool cand[4]; // 使える色の候補 memset( cand, true, sizeof(cand) ); // 隣り合うポイントを調べてく if( y > 0 ){ cand[P[y-1][x]] = false; // 上 } if( y < R - 1 ){ cand[P[y+1][x]] = false; // 下 } if( x > 0 ){ cand[P[y][x-1]] = false; // 左 } if( x < W - 1 ){ cand[P[y][x+1]] = false; // 右 } if( y > 0 && x > 0 && cells[y-1][x-1] == 'N' ){ cand[P[y-1][x-1]] = false; // 左上 } if( y > 0 && x < W - 1 && cells[y-1][x] == 'Z' ){ cand[P[y-1][x+1]] = false; // 右上 } if( y < R - 1 && x > 0 && cells[y][x-1] == 'Z' ){ cand[P[y+1][x-1]] = false; // 左下 } if( y < R - 1 && x < W - 1 && cells[y][x] == 'N' ){ cand[P[y+1][x+1]] = false; // 右下 } int cn = 0; int color = 0; for( int i = 1; i <= 3; i++ ){ if( cand[i] ){ cn++; color = i; } } // すべての色を使い切ってたらアウアウ if( cn == 0 ){ return "No"; } // 候補が1つだけなら色を塗る if( cn == 1 ){ P[y][x] = color; cul++; } } } } // すべての格子点を塗りつぶせたらセフセフ return "Yes"; } };