What cases are impossible?

What cases require no flips?

How many flips do you need to move the light over?

If ~M = 1~, the case is impossible. If ~N = 1~, the case is impossible unless ~M = 2~. Otherwise, we require that ~N+M \equiv 1 \pmod 2~.

Why? Note that for a cell for ~(r, c)~, we always enter it from one of two directions. If ~r+c \equiv 0 \pmod 2~ we enter from above or below, but never from the left or right, and the opposite is true if ~r+c \equiv 1 \pmod 2~.

Consider the set of cells that we enter from above. Initially we enter ~(1, 1)~, but without flipping anything we enter ~(x, x)~ from above for all ~x~. We want to get to ~(N+1, M)~, so if ~N+1 = M~ we can win without flipping any mirrors.

We can flip two mirrors to move two spots down or left. Effectively this means that we can change from being at the diagonal beginning at ~(1, 1)~ to the one at ~(1, 3)~ or ~(3, 1)~. Since we want to reach ~(N+1, M)~, our answer is ~\max(N+1-M, M-(N+1))~.

Build a graph for the input.

Our nodes are ~(cell, direction)~.

If the light hits a mirror twice, should we flip that mirror?

If the light hits a mirror twice, we should not flip that mirror. Similarly, If we flip a mirror and the light's path hits that mirror twice, we would've been better off not hitting the mirror at all.

Also, the parity mentioned in the first subtask guarantees that the light will never bounce back on itself, which together guarantee that any cycles we run into can be safely ignored.

All of this is to say that we can simply run ~0-1~ BFS on the specified graph to get our answer. Dijkstra should still pass though it is comparably inefficient.