Cows on Skates

After years of pleading, Farmer John finally gave in and bought roller skates for the entire herd of cows. Much of the farm is perfect for roller-skating, but a few squares have far too many rocks and cannot be crossed on skates.

The farm is represented as a grid with $R$ rows and $C$ columns ($1 \le R \le 113$, $1 \le C \le 77$). Around feeding time, Bessie finds herself at square $(1, 1)$ and wants to get back to the barn at square $(R, C)$. She may skate only between orthogonally adjacent squares (sharing an edge, never diagonally) that do not contain rocks. It is guaranteed that at least one such route from $(1, 1)$ to $(R, C)$ exists.

Here $(r, c)$ denotes the square in row $r$ and column $c$, with rows numbered from $1$ at the top and columns from $1$ at the left.

• Line 1: two space-separated integers $R$ and $C$.
• Lines $2 \ldots R+1$: each line contains $C$ characters with no spaces. Each character is either '.', meaning Bessie can skate on that square, or '*', meaning the square has too many rocks. The $j$-th character of the $i$-th of these lines describes square $(i, j)$. Squares $(1, 1)$ and $(R, C)$ are always '.'.

Output the shortest path from $(1, 1)$ to $(R, C)$. A path is a sequence of squares that starts at $(1, 1)$ and ends at $(R, C)$, in which consecutive squares are orthogonally adjacent (sharing an edge) and no square is a rock. The shortest path is the one containing the fewest squares.

If several shortest paths exist, output the lexicographically smallest one. Compare the two paths as sequences of squares from the beginning; each square is treated as the pair $(\text{row}, \text{column})$ and pairs are compared by row first, then by column.

Print the squares of the path one per line, each as two space-separated integers 'row col'. The first line must be '1 1' and the last line must be 'R C' (that is, $R$ and $C$).