マス \((i,j)\) の左辺の中点を端点とする線分が存在するかどうかを \(C_{i,j}\) で表すことにします（存在する場合 \(1\)、存在しない場合 \(0\)）。 \(C_{i,0}\) を決めると \(C_{i,1}, C_{i,2}, \ldots,C_{i,W-1}\) が全て一意に定まります。 具体的には、\(S_{i,j}\) が A のとき \(C_{i,j+1}=1-C_{i,j}\)、\(S_{i,j}\) が B のとき \(C_{i,j+1}=C_{i,j}\) です。 なお、\(S_{i,0}, S_{i,1}, \ldots, S_{i,W-1}\) に含まれる A の個数が奇数である場合、条件を満たすタイルの置き方は存在しません。

列についても同様に考えると、全部で \(2^{H+W}\) 通りの置き方があるように思えますが、\(S_{i,j}\) が B であるとき、タイル \((i,j)\) の周りの \(4\) 箇所が全て \(0\) だったり、全て \(1\) だったりしてはいけないので、行 \(i\) の \(01\) 列を決めると、列 \(j\) の \(01\) 列も一意に定まります。これらの条件を二部グラフで表し、矛盾がない場合、二部グラフの連結成分の数を \(S\) として、答えは \(2^S\) となります。