赤色を1, 白色を0とする。すると4種類のコマは
0 0 1 1 0 1 1 0 0 1 0 1 1 1 0 0
となる。要するに、左右と上下は独立。
ここで、線がつながってることに注目。すると、とある列/行だけ取り出した時の値は
0 1 1 0 0 1 1 0 0 1 ... みたいになってる。つまり最初が0か1かでその列は一意に決まる。
よって、本質的には長さHの数列 a_i とWの数列 b_i だけを考えれば良い。値は0か1だけである。
よって、サイクルがあるとNGという条件を無視すると、答えは 2H+W.
ここで、"サイクルがある"と"長さ4のサイクルがある"は同値であることに注目。証明は略。
そして、"長さ4のサイクルがある" と "a_i = a_i+1, b_j = b_j+1, ((a_i) + j) % 2 == ((b_j) + i) % 2, なるi, jが存在"は同値であることが示せる。
あとはちょっと実装が重いDP。
