Piece it together (UVa Live Archive Europe Northwestern 2011)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3914

問題

図のようなブロックを使って指定されたように敷き詰めることができるか？
1<=n,m<=500

解法

まず、白のブロック数が黒のブロック数の2倍でなければNO。
ブロックの形をよく見てみると、あるBから右側のWを使う場合は左側のWは使えず、左側のWを使う場合は右側のWは使えない。また、必ずどちらかのWを使う必要がある。上下についても同様なので、これは2-SATとみなすことができる。あとは2-SATを解くだけ。dfsでやるとスタックオーバーフローする可能性があるのでなるべくループでやること。