上から1行ずつ塗り方を決めるDPを考えます。

「行の塗り方及び連結成分の属し方」をキーとし、そのような塗り方の個数と連結成分数の和を値に持つDPにより問題を解くことができます。

実装によっては、以下の例のようなケースで連結成分の管理に注意してください。

例：1マス目と3,5マス目でそれぞれ連結成分をなしているとき、次の行の1,2,3,5マス目を塗ると、これらは全て同じ連結成分に属する

A.B.B
###.#

「行の塗り方及び連結成分の属し方」の個数は緩い上界がベル数 \(B_W\) であることから状態数は \(O(HB_W)\) であり、遷移は \(\tilde{O}(W2^W)\) なので、全体で \(\tilde{O}(HWB_W2^W)\) 時間でこの問題を解くことができます。\(B_7=877\) であることから、制約のもとこの解法は十分高速です。

類題：TDPC S『マス目』