Minimum Steps in a Land Maze

You are given a square grid of size \(N\times N\) representing a map, where each cell is either land (L) or water (W). Your task is to find the minimum number of steps required to travel from the top-left cell at \((0,0)\) to the bottom-right cell at \((N-1, N-1)\) using only the four cardinal directions (up, down, left, right) on cells that contain land.

Note:

• If the starting cell or the destination cell is water, or if there is no valid path from start to destination, output Impossible.
• Each step moves you from one cell to an adjacent cell.

The problem may contain multiple test cases. For each test case, you will be given an integer N followed by N lines describing the grid. The sequence of test cases terminates with a line containing 0. The output for each test case should be printed on a new line.

inputFormat

The input is read from standard input (stdin) and consists of one or more test cases. Each test case is formatted as follows:

N
row1
row2
... 
rowN

where N (an integer) represents the dimensions of the grid, and each row contains exactly N characters (either L or W). The end of test cases is signaled by a line containing 0.

outputFormat

For each test case, output a single line to standard output (stdout) containing the minimum number of steps required to reach the destination. If it is not possible to reach the destination, output Impossible.

5
LLLWL
LWWLL
LWLWL
LLWLL
LLLLL
0

8