Huge Parking Lot

Time limit2sMemory limit512 MB

Summary

In a full grid of cars, pillars, and one free exit cell, slide cars one at a time to bring car X to the exit with the fewest moves.

Level: Medium7 of 10
Topics: BFS, Graph, Greedy, Implementation
Solved: No attempts yet

Problem

John works at a huge parking lot. The lot is a rectangular field of size $n \times m$ , divided into $n \times m$ square cells of size $1 \times 1$ . One of the corner cells holds the exit from the lot.

There are many cars in the lot, so getting a car out is not so simple. The only thing John can do is move one car to an adjacent cell, provided that cell is free. Cells that share a side are adjacent. The task gets harder because of the pillars in the lot. A car cannot be placed on a cell that holds a pillar. The lot is completely filled with cars and pillars, and the only free spot is the exit. John's goal is to drive one car out of the lot. Help him find the minimum number of moves he will have to make.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 50$ ), the dimensions of the lot. Then follow $n$ lines of $m$ characters each. The character <<.>> denotes a free cell; the single free cell is the exit from the lot. The character <<#>> denotes a pillar. Pillars cannot be moved, and cars cannot be placed on a pillar. The character <<c>> denotes a car. The character <<X>> denotes the car that must be driven out of the lot. A car counts as driven out as soon as it reaches the exit. At least one of $n$ and $m$ is greater than one, and each of the characters <<.>> and <<X>> appears in the input exactly once. The character <<.>> is always in the top left corner of the lot.

Output

If the car cannot be driven out, output the single word <<Impossible>>. Otherwise output a single number on one line: the minimum number of moves needed to drive the car out.

Examples2

Example 1
Input
```
3 3
.#X
ccc
c#c
```
Expected output
```
Impossible
```
Example 2
Input
```
2 3
.cX
ccc
```
Expected output
```
7
```