The correct solution is a greedy algorithm, that tries to put mirrors in such way that every light beam goes as much as possible upwards. We will successively track beams lighted into gaps with numbers ~1, 2, \dots, n+m~.

Let us consider the following algorithm:

1. Let ~x, y~ be the current column and row of the tracked beam. Let ~x', y'~ be the column and row of the gap through which the beam should leave.
2. If ~x = x'~ and ~y = y'~ then stop.
3. If beam goes vertically go to point 5.
4. If there is a mirror above the current position and ~x \ne x'~ or ~y = y'~ go one cell to the right: ~x := x+1~. Otherwise, place mirror in the cell ~x, y~ and go one cell up: ~y := y-1~. Go back to point 2.
5. If there is a mirror in the current cell, go right: ~x := x+1~. Otherwise go up: ~y := y-1~. Go back to point 2.

To prove the correctness of this algorithm, we will consider the only bad situation:

The beam should leave with the gap above, but on the way there is a mirror ~B~. This situation can not occur because there is no light reflected by the upper side of a mirror ~A~. And in our algorithm the mirror is placed only when the beam is reflected.