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)のマス目がある。

それぞれのマスのそれぞれの辺は、白い線となっている。加えて、それぞれのマスの、２つの対角線のうち、１つだけ白い線が引かれている。２つの格子点は白い線で結ばれている場合、それは隣接していると言われる。

私たちは赤、緑、青の３つの色を使って格子点を全て塗りたい。ただし、１つだけ制約があり、それは隣り合う格子点には、同じ色を使ってはならない、というものである。

あなたには、W文字の文字列がH個ある String[] cellsが与えられる。cells[i][j]が'N'であれば、マス[i][j]は左上から右下に向かって白い線で対角線が引かれているし、'Z'であれば、右上から左下に向かって白い線で対角線が引かれている。

全ての格子点が３色のどれかで塗りつぶせるのであれば"Yes"を、できないようならば"No"を返せ。

制約

1 <= H, W <= 50

考えた事

どこかの２つの隣り合う格子点に対し、塗る色を決めてしまう。そうすると、格子点の中で、塗るべき色が一意に決まるところがでてくる。そうゆう格子点にどんどん色を塗っていき、全て塗りきったらセフセフ。隣り合う格子点が３色使っている格子点がでてきたらアウアウ。

事後

もっと簡潔にかけるらしく、ある格子点に着目したとき、その格子点が属している４つのマスで、'Z'が１つ、または３つであれば、アウアウ！（なんで！？）

ソースコード

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";
                    }

                    // 候補が１つだけなら色を塗る
                    if( cn == 1 ){
                        P[y][x] = color;
                        cul++;
                    }
                }
            }
        }

        // すべての格子点を塗りつぶせたらセフセフ
        return "Yes";
    }
};