TopCoder SRM 587 Div2 Hard ThreeColorabilityEasy

さてDiv2 Hard。
今回妙に簡単だな…。いや、２回凡ミスしたんだけど。
http://community.topcoder.com/stat?c=problem_statement&pm=12699

問題

(0,0)-(H,W)上の格子点を考える。
隣り合う格子点同士を辺でつなぎ、グリッド状にする。
このときできる個々の1x1の正方形について、左下から右上または右下から左上のいずれか対角線を引くように辺でつなぐ。

辺同士でつながった点同士が同じ色にならないように、点を塗り分ける。
点を３色で塗り分けられるか答えよ。

解法

グリッドを構成する各正方形を考える。２点の色が決まると４点の色が確定する。
よって、一番左上の正方形だけ各点の色を決めてしまい、後は接する正方形の色をどんどん確定させていく。
隣同士の正方形は２点を共有するので、ある正方形の４点の色が確定すれば、隣も確定できる。

あとは辺でつながった点が同じ色にならないか適宜チェックしていけばよい。

class ThreeColorabilityEasy {
	public:
	int col[52][52];
	string isColorable(vector <string> cells) {
		int H=cells.size();
		int W=cells[0].size();
		int x,y;
		ZERO(col);
		
		col[0][0]=1;
		if(cells[0][0]=='N') {
			col[1][0]=2;
			col[0][1]=2;
			col[1][1]=3;
		}
		else {
			col[1][0]=2;
			col[0][1]=3;
			col[1][1]=1;
		}
		
		
		FOR(y,H) FOR(x,W) {
			if(x==0 && y==0) continue;
			if(col[x][y]==col[x][y+1]) return "No";
			if(col[x][y]==col[x+1][y]) return "No";
			if(cells[y][x]=='N') {
				if(col[x+1][y]==0) col[x+1][y]=col[x][y+1];
				else if(col[x][y+1]==0) col[x][y+1]=col[x+1][y];
				col[x+1][y+1]=6-col[x][y]-col[x][y+1];
			}
			else {
				if(col[x+1][y]==col[x][y+1]) return "No";
				if(col[x+1][y]==0) col[x+1][y]=6-col[x][y]-col[x][y+1];
				if(col[x][y+1]==0) col[x][y+1]=6-col[x][y]-col[x+1][y];
				col[x+1][y+1]=col[x][y];
			}
		}
		FOR(y,H) if(col[W][y]==col[W][y+1]) return "No";
		FOR(x,W) if(col[x][H]==col[x+1][H]) return "No";
		return "Yes";
	}
};

まとめ

今回はどれもあっさり解けてうれしい。なぜ参加できなかった…。