Grid Jumps

Interview

Time limit2sMemory limit256 MB

Summary

Find the fewest digit-length jumps from the top-left cell to the bottom-right cell of a grid, or print IMPOSSIBLE.

Level: Medium4 of 10
Topics: BFS, Graph
Solved: No attempts yet

Problem

Each square of an $n \times m$ grid holds one digit. From a square holding the digit $k$ , a move jumps exactly $k$ squares up, down, left, or right, and counts as one move. A move may not leave the grid, and the grid does not wrap from one edge to the opposite one.

Find the minimum number of moves needed to get from the top left square to the bottom right square.

Input

The first line contains two space separated integers $n$ and $m$ ( $1 \le n, m \le 500$ ), the size of the grid. At least one of $n$ and $m$ is greater than 1.

Each of the next $n$ lines contains $m$ digits with no spaces. Every digit is between 0 and 9, inclusive.

The first character of the first line is the top left square, and the last character of the last line is the bottom right square.

Output

Print, on a line by itself, the minimum number of moves needed to get from the top left square to the bottom right square. If the bottom right square cannot be reached, print IMPOSSIBLE.

Examples3

Example 1
Input
```
2 2
11
11
```
Expected output
```
2
```
Example 2
Input
```
2 2
22
22
```
Expected output
```
IMPOSSIBLE
```
Example 3
Input
```
5 4
2120
1203
3113
1120
1110
```
Expected output
```
6
```