本問を，最小頂点被覆問題に帰着させて解く方法を解説します．

---

最小頂点被覆問題とは

まず，簡単に最小頂点被覆問題とは何かについて解説します．最小頂点被覆問題とは，以下のような問題のことを指します．

グラフがあり，その頂点の部分集合 \(V\) を考える．このとき，\(V\) について，次の条件が成立している必要がある．

• グラフ上の全ての辺に対して，その端点の少なくとも一方の頂点は \(V\) に含まれる．

このとき，\(V\) に含まれる頂点数として考えられる最小値はいくらか？

この問題は，一般のグラフにおいてはNP困難であるため，厳密解を求めることは困難です．しかし，グラフの形状が特殊である場合，厳密解を容易に求めることができる場合があります．具体的には，次の事実が成り立ちます．

二部グラフの最小頂点被覆問題の答えは，最大マッチングの大きさに等しい．

この問題においては，上記の事実がわかっていれば解くのには十分であるため，詳細は省略します．（参考：二部グラフの最小点被覆，最大安定集合，最小辺被覆の求め方）以降では，本問を最小頂点被覆問題に帰着させて解くには具体的にどのようにすればよいかについて解説します．

---

解法

まず，あるマスについて，上下方向を監視する場合，上下方向に繋がっているマスで，障害物に遮られない範囲すべてを監視してよいと言えます．

そこで，上下方向に繋がっており，障害物によって遮られないマスの範囲の中で極大のものを，連結範囲と呼ぶことにします．このとき，障害物の置かれていないマスすべてに対して，そのマスが属する連結範囲が必ず一つだけ存在することが容易にわかります．以下，上下方向の連結範囲の集合を \(S\) とし，マス \((i,j)\) が属する連結範囲を \(S_{i,j}\) とおきます．

ここで，障害物の置かれていないマス \((i,j)\) 全てに対して，\(S_{i,j} \) を求めましょう．これは，グリッドを端から順番に見ていくことにより， \(O(HW)\) でできます．問題文中の入力例2の例を，下図に示します（同じ番号が書かれているマスが，同じ連結範囲であることを表します）．

左右方向についても全く同様に議論できます．以下，左右方向の連結範囲の集合を \(T\) とし，マス \((i,j) \) が属する連結範囲を \(T_{i,j}\) とします．上下方向と同様に，問題文中の入力例2の例を，下図に示します．

先述の議論の通り，上下方向・左右方向ともに，監視は連結範囲に対して行うものを考えれば十分です．一方で，本問では，障害物の置かれていないマスすべてを監視する必要があります．これは，次のように言い換えられます：

\(S, T\) に属する連結範囲それぞれについて，「監視する」か「監視しない」を選ぶことができる．ただし，障害物の置かれていないマス \((i,j)\) すべてに対して，次が成り立っている必要がある．

• \(S_{i,j}\) と \(T_{i,j}\) のうち，少なくとも一方は監視されている．
  

このとき，「監視する」連結範囲の個数の最小値を求めよ．

これは，\(S,T\) の成分それぞれを頂点とみなし，障害物の無いマス \((i,j)\) のすべてに対して \(S_{i,j}\) と \(T_{i,j}\) の間に辺を張ったグラフを考えたとき，まさにそのグラフの最小頂点被覆問題そのものです．また，このグラフの辺は必ず \(S\) 上の頂点と \(T\) 上の頂点を結ぶため，このグラフは二部グラフとなります．例えば，入力例2においては次のようなグラフとなります．

したがって，このグラフの最大マッチングの大きさを求めればよく，これは最大流を使うことでできます．例えば，入力例2の場合において考えた上記のグラフの最大マッチングの大きさは \(5\) であり，まさにこの場合の答えに一致していることがわかります．

最小頂点被覆問題の類題：yukicoder No.1479「Matrix Eraser」

実装例（C++）