Problem 5

Assume $M_1=(2,1)$; the right-edge case is its mirror image. On attempt 2 enter row 2 at $(2,2)$, visit $(2,3)$ and return to $(2,2)$, then descend to $(3,2)$. In each row $r=3,\ldots,s-2$, enter at $(r,r-1)$, visit $(r,r)$ and $(r,r+1)$, return to $(r,r)$, and descend to $(r+1,r)$. In the last monster row enter $(s-1,s-2)$, visit $(s-1,s-1)$, and then descend to the goal row. This is the staircase. If it is clear, Turbo wins on attempt 2. If it first meets $M_2$ at a downward entry $(r,r-1)$, then the already visited shoulder $(r-1,r)$ is safe; on attempt 3 follow the safe prefix to that shoulder, enter row $r$ at $(r,r)$, move west to column 1, and descend column 1. If $M_2$ is met on one of the horizontal steps instead, the cell immediately to its west is safe; reproduce the prefix to that cell, move west to column 1 in row $r$, and descend. In either subcase, every other cell of row $r$ is safe because it contains the unique monster $M_2$ of that row, and column 1 is safe below row 2 because it already contains $M_1$. Thus the third path reaches the goal. This gives a completely specified strategy in at most 3 attempts.