Minimum Moves in a Grid

You are given an \(R \times C\) grid representing a maze. Each cell in the grid is either open (denoted by .) or blocked (denoted by #). The robot starts at the top-left cell (position \((0,0)\)) and its goal is to reach the bottom-right cell (position \((R-1, C-1)\)).

The robot can move one cell at a time in one of the four directions: up, down, left, or right. The number of moves is simply the number of steps taken. Formally, if \(m\) is the minimum number of moves needed, you are to compute \(m\) such that the path is valid, or output impossible if there exists no valid path.

Input Format: Multiple datasets where each dataset begins with a line containing two integers \(R\) and \(C\) (with \(1 \leq R, C \leq 1000\)). The next \(R\) lines represent the grid. The input terminates with a line containing "0 0".

Output Format: For each dataset, print the minimum number of moves required to reach the destination. If the destination cannot be reached, print impossible.

inputFormat

The first line of each dataset contains two integers \(R\) and \(C\) separated by a space. This is followed by \(R\) lines, each consisting of a string of \(C\) characters (each character is either . for an open cell or # for an obstacle). The input ends when a line containing "0 0" is encountered.

outputFormat

For each dataset, output a single line. If there is a path from the start to the destination, output the minimum number of moves required. Otherwise, output impossible.

## sample

5 5
.....
.#.#.
.#.#.
.#.#.
.....
0 0

8

</p>