Curling 2.0

On Planet MM-21, curling has become popular after this year's Olympic games, though the rules differ from ours. The game is played on an ice board marked with a square grid, and it uses a single stone. The goal is to move the stone from the start square to the goal square in the minimum number of throws.

Some squares of the board are occupied by blocks. Two special squares, the start and the goal, are never occupied by blocks and are always distinct. Once the stone begins to move it keeps going until it hits a block; to steer it toward the goal you may need to stop it against a block and throw again.

Fig. D-1: Example board (S: start, G: goal)

The stone moves according to the following rules:

• At the beginning the stone rests on the start square.
• The stone may move only along the x or y axis. Diagonal moves are not allowed.
• While the stone is at rest you can set it moving by throwing it. You may throw it in any direction unless that direction is blocked immediately (by an adjacent block).
• Once thrown, the stone keeps moving in the same direction until one of the following happens:
  • It hits a block. The stone stops on the square just before the block, and that block disappears.
  • It leaves the board. The game ends in failure.
  • It reaches the goal square. The stone stops there and the game ends in success.
• You may throw the stone at most 10 times per game. If the stone has not reached the goal within 10 throws, the game ends in failure.

Fig. D-2: Stone movements

Under these rules, determine whether the stone can travel from the start to the goal and, if so, the minimum number of throws required. For the example board, 4 throws are needed; note that the block configuration changes as blocks are destroyed along the way.

Fig. D-3: A solution for the example board and the resulting configuration

The input is a sequence of datasets. The end of the input is a line containing two zeros separated by a space. The number of datasets never exceeds 100.

Each dataset has the following format:

w h
row 1
...
row h

The first line gives the width $w$ and the height $h$ of the board, satisfying $2 \le w \le 20$ and $1 \le h \le 20$. Each of the next $h$ lines contains $w$ integers separated by spaces, describing one row of the board. Each integer describes the status of the corresponding square:

For each dataset, print a single line containing the minimum number of throws needed to move the stone from the start to the goal. If no such route exists, print -1 instead. The line must contain nothing but this number.