この問題は次のようにしてマッチングの問題に定式化できます。

各マスに対応する頂点を用意する。隣接する2マスでありどちらも 1 でないとき、対応する頂点の間に辺を張る。このグラフのマッチングであって、2 が書かれている頂点全てがマッチングに含まれるようなものは存在するか？

入力例1に対応するグラフ

このグラフは二部グラフであることから、この問題はさらに次のようなフローの問題に置き換えることができます。

前述の通り作った二部グラフの頂点集合を \(A,B\) とする。既存の辺は \(A\) から \(B\) への有向辺とする。頂点 \(S,T\) を追加し、\(S\) から \(A\) の各頂点へ、\(B\) の各頂点から \(T\) への頂点を追加する。全ての辺の容量を \(1\) とする。\(S\) から \(T\) へのフローであって、2 が書かれている頂点全てについて、その頂点と \(S\) または \(T\) を結ぶ辺の流量が \(1\) であるようなものは存在するか？

入力例1に対応するグラフ

この問題は最小流量制限つき(最大)フロー問題にほかならないので、最大流を求めるアルゴリズムを用いて解くことができます。

フローを求めるグラフは全ての辺の容量が \(1\) であり、辺数が \(O(HW)\) であることから、Dinic法により \(O((HW)^{1.5})\) でこの問題を解くことができました。

Writer解(C++)

最小流量制限つき最大流問題

\(S\) から \(T\) への最大流を求める問題において、辺に最小流量制限があるケースを、制限のない最大流問題に帰着する方法を説明します。
容量が \(R\) で最小流量制限が \(L\) である \(u\) から \(v\) へ辺について考えます。最小流量制限を処理する新たな頂点 \(S',T'\) を作成し、もとの辺を削除して、下図の通りの容量のをもつ辺を張ります。

最小流量制限を持つ全ての辺に対してこの処理を行い、できたグラフにおいて、

• \(S'\) から \(T'\) へ
• \(S'\) から \(T\) へ
• \(S\) から \(T'\) へ
• \(S\) から \(T\) へ

の順にそれぞれフローを流し、\(S'\) から出る辺と\(T'\) へ入る辺の全てで流量と容量が一致していることが、最小流量制限を満たすような\(S-T\) フローが存在することと同値になります。（\(S',T'\) を出入りするフローと、元の辺のフローを付け替えることを考えるとわかります）

また、最大流を求めるのではなく「最小流量制限を満たすようなフローが存在するか」を判定するだけであれば、フローを \(4\) 回求める代わりに、\(T\) から \(S\) に容量無限の辺を張った上で、\(S'\) から \(T'\) へのフローを \(1\) 回求めるだけで同じように判定できます。

参考文献：

• 最小流量制限付き最大流 (snuke さんのブログ)
  
• 『プログラミングコンテストチャレンジブック　第2版』P193