列ごとに順にみていき，その時点での連結の状態を持つ，次の DP を行います．

• \(dp[i][S] = \)(\(i\) 列目までのマスの塗り方を決めたとき，\(i\) 列目における連結の状態が \(S\) であるようなマスの塗り方の数)

ここで，「連結の状態」とは，どのマスとどのマスが同じ連結成分に属しているかを表します．例えば，\(1, 3\) 行目のマスと \(5, 6\) 行目のマスが黒マスでそれぞれ同一の連結成分に属し，\(2, 4\) 行目のマスは白マスである，という場合には，\((1, 0, 1, 0, 2, 2)\) などのように，行の状態を番号で表すようにするのが便利です．以下，番号には次のような意味を持たせるということでルール付けしておきましょう．

• \(0\)：白マス
• \(1\)：左上のマスと同一の連結成分に属する黒マス
• \(2, 3\)：左上のマスと異なる連結成分に属する黒マス．同一の連結成分に属するマスは同一の番号で，異なる連結成分に属するマスは異なる番号で表すようにする．（同一の列に共存できる連結成分の数は高々 \(3\) 個なので，\(4\) 以上の番号が付与されることはありません）

このルール付けのもとで，連結の状態の数の明らかな上界として \(4^H\) があります．\(0\) から \(3\) までの番号が \(H\) 行それぞれに振られるからです（実際にはもっと少なくなりますが）．

DP の遷移を行う際は，今見ている列の連結の状態と次の列の塗り方を見て，次の列の連結の状態を求めます．これは，Union-Find などを用いて連結状態を管理したのち，座標圧縮などを用いて正規化することによって可能です．

最後の列まで DP を遷移させたときに，右下のマスの番号が \(1\) であるようなものが答えです．計算量は，状態数が \(O(W4^H)\)，\(1\) つの状態からありえる遷移が \(O(2^H)\) であるため，例えば \(1\) 回の遷移の際の計算を \(O(H \log H)\) とした場合 \(O(HW8^H \log H)\) などとなります．