The idea of this problem was originally proposed by Keyence.

This problem can be boiled down to a maximum flow problem.

Instead of placing a camera facing up on a square, we can place a camera facing down on the topmost square above the original square without reducing the monitored squares. Therefore, we can assume that we never use a camera facing up in the optimal solution. Same applies for those facing left.

When a camera facing down is placed on a square, if the adjacent square above does not have a obstacle, we can shift the camera one square above without reducing the monitored squares. Therefore, we can assume that the square with a camera facing down has always an adjacent square above with an obstacle. Same applies for those facing right.

For each square \(c\), let \(X_c\) be a boolean variable representing whether to place a square facing down, and \(Y_c\) be that facing right.

Each square \(c\) must be monitored by a camera. Let \(f(c)\) be the furthest square above \(c\) (= the square to place a camera facing down that can monitor \(c\)) and \(g(c)\) be the furthest square in the left of \(c\). Then problem is formalized as follows.

Find the minimum cost to assign boolean values to \(X_c\) and \(Y_c\) so that:

• for each \(c\), if \(X_c\) is true, then a cost of \(1\) is incurred;
• for each \(c\), if \(Y_c\) is true, then a cost of \(1\) is incurred;
• for each \(c\), it must not happen that both \(X_{f(c)}\) and \(Y_{g(c)}\) are false (\(\Leftrightarrow\) setting both \(X_{f(c)}\) and \(Y_{g(c)}\) costs \(\infinity\))

Since the third constraint is a submodular function on \((\lnot X_{f(c)},Y_{g(c)})\), we can boil it down to a max-flow problem by letting \(X_c\) be the negation of \(X_c\) anew, for all \(c\). Specifically, the maximum \(S-T\) flow on the following graph is the sought answer. (We identify the variables \(X_c\) and \(Y_c\) with the corresponding vertices.)

• For each \(c\), add an edge from \(S\) to \(X_c\) with capacity \(1\);
• for each \(c\), add an edge from \(Y_c\) to \(T\) with capacity \(1\);
• for each \(c\), add an edge from \(X_{f(c)}\) to \(Y_{g(c)}\) with capacity \(1\).

This graph has \(O(HW)\) vertices and \(O(HW)\) edges, and the flow passing through any vertices other than \(S\) and \(T\) is at most \(1\), so we can find the maximum flow with Dinic’s algorithm in a total of \(O((HW)^{1.5})\) time.

(Instead of boiling down to a maximum flow problem, we can consider it as a minimum point cover problem, which yields the same solution.)

Sample code (C++, with ACL)