Processing the map from left to right, we need to keep track if there is a guard placed behind us (to the left) on the top row and bottom row.

If there isn't and this is a free square, we need to place one guard. Then we need to do some case analysis depending on the top and bottom squares being free or not.

The caveat is that we need to pick carefully when a guard is controlling a square above/below his row. I used 3 states for each of the rows: NONE = no guard, HAS_USED = placed a guard and it is guarding a row above/below him, HAS = I need to place a guard here. Take a look at this example:

...#.#
......

We need to place a guard both on the top and bottom rows, but we can preserve both rows with "HAS" state. Then, when we process the second to last column, we assign that square to the guard on the bottom row.

This takes O(N). Here's my code http://ideone.com/Q1ebEu

Another way to solve it with dp, with O(N^2) complexity — DP[i][j] is for smallest number of guards needed to cover i cells in first row and j cells in second row. When trying to extend your state, you can either move by 1 cell for free, if that cell contains #, or cover that cell by placing guard either in this cell or in matched cell in other row (just don't forget to update information about covered cells in other row). Code.

Actually it is the same with greedy approach. Because each segment of length one will have degree at most one, so the MM can be found greedy.

Is the same problem on a NxM grid solvable in polynomial time?

Then, add an edge between a left vertex and a right vertex iff the corresponding segments share an edge and exactly one of them has length one.

Why exactly one of them should have length one? even if both of them have length one, we will still need to do a bipartite matching of them. The answer is then, the no. of segments in the grid-the result we find from bipartite matching.

Please tell me where am I going wrong in this.