この問題の原案はキーエンスから提供されました。

この問題は最大流問題に帰着して解くことができます。

あるマスに上向きの監視カメラを置くかわりに、そのマスから監視することができる最も上にあるマスに下向きの監視カメラを置いても監視することができるマスは減りません。よって最適解において、上向きの監視カメラを使うことはないとしてよいです。左向きについても同様です。

あるマスに下向きの監視カメラを置くとき、その1つ上のマスに障害物がなければ、監視カメラを置くマスを1つ上に変えても監視することができるマスは減りません。よって最適解において、下向きの監視カメラが置かれるマスは、障害物があるマスの直下に限るとしてよいです。右向きについても同様です。

各マス \(c\) に対し、下向きの監視カメラを置くかどうかを表す真偽値変数を \(X_c\)、右向きの監視カメラを置くかどうかを表す真偽値変数を \(Y_c\) とします。

各マス \(c\) はいずれかの監視カメラに監視されている必要があります。\(f(c)\) を \(c\) から上方向に最も遠いマス(= 下向きの監視カメラで \(c\) を監視する際に監視カメラを置くマス)、\(g(c)\) を \(c\) から左方向に最も遠いマスとします。このとき問題は次のように定式化されます。

以下の条件を全て満たすように \(X_c,Y_c\) に真偽値を割り当てるときの最小コストを求めよ。

• 各\(c\) について、\(X_c\) が真ならば \(1\) のコストがかかる
• 各\(c\) について、\(Y_c\) が真ならば \(1\) のコストがかかる
• 各 \(c\) について、\(X_{f(c)}\) と \(Y_{g(c)}\) がともに偽であってはならない(\(\Leftrightarrow\) \(X_{f(c)}\) と \(Y_{g(c)}\) がともに偽のとき \(\infty\) のコストがかかる)

3番目の制約は \((\lnot X_{f(c)},Y_{g(c)})\) に関する劣モジュラ関数であることから、全ての \(c\) について \(X_c\) の真偽値を反転したものを改めて \(X_c\) と置き直すことで、最大流問題に帰着して解くことができます。具体的には、次のようなグラフの \(S-T\) 最大流が求める答えになります。（変数 \(X_c,Y_c\) と、それに対応する頂点を同一視しています）

• 各 \(c\) について、\(S\) から \(X_c\) に容量 \(1\) の辺を張る
• 各 \(c\) について、\(Y_c\) から \(T\) に容量 \(1\) の辺を張る
• 各 \(c\) について、\(X_{f(c)}\) から \(Y_{g(c)}\) に容量 \(\infty\) の辺を張る

このグラフは頂点数 \(O(HW)\)、辺数 \(O(HW)\) であり、\(S,T\) を除く全ての頂点についてその頂点を通る流量が高々 \(1\) であることから、dinic法により \(O((HW)^{1.5})\) で最大流を求めることができます。

（なお、最大流問題に帰着する部分は、最小点被覆を求めると考えることもでき、同じ解法になります）

実装例(C++, with ACL)