在行星MM-21上，今年奥运会之后，冰壶（curling）越来越受欢迎。 但规则与我们有所不同。 该游戏是在冰盘上进行的，在冰棋盘上标有方形网格。他们只用一块石头。 游戏的目的是以最少的动作（ the minimum number of moves.）让石头从开始到目标位置。
Fig. 1 是游戏板的示例。 一些方块可能被石块占据。 有两个特殊的方格即开始和目标，没有被块占据。 （这两个方块是不同的。）这两个方块是不同的。）一旦石头开始移动，它将继续进行，直到它撞到一个石块。为了把石头带到目标位置，你可能必须通过击中石块来阻止石块，并重新抛出。
Fig. 1: Example of board (S: start, G: goal)
石头的运动遵从以下规则：
- 一开始，石头会在起始方块。
- 石头的运动限于x和y方向。 对角线移动是禁止的。
- 当石头静止时，你可以通过扔它移动。 除非立即被阻止，否则您可以将其扔到任何方向（图2（a））。
- 一旦投掷，石头会继续向同一方向移动，直到发生以下情况之一：
- 石头撞上一块（图2（b），（c））。
- 石头停在撞击它的石块的旁边的正方形上。.
- 石块消失
- 石块从木板上掉出来
- 游戏结束
- 石头到达目标位置
- 石头停在那里，游戏结束了。
- 你不能在比赛中扔石头10次以上。 如果石头在10次移动中没有达到目标，游戏就会失败。
Fig. 2: Stone movements
根据规则（under the rules），我们想知道一开始的石头是否可以达到目标，如果是，则需要最少的移动次数。
在图1所示的初始配置中，需要4次移动才能将石头从开始位置移动到目标位置。 路线如图3（a）所示。 注意当石头到达目标时，游戏板配置如图3（b）所示。
Fig. 3: The solution for Fig. D-1 and the final board configuration
Input
输入是一系列数据集。 输入的结尾由包含由空格分隔的两个零的行指示。 数据集的数量从不超过100。
每个数据集格式如下。
the width(=w) and the height(=h) of the board
First row of the board
...
h-th row of the board
板的宽度和高度满足:2 < = w < = 20,1 < = h < = 20。
每一行都由一个空格分隔的w十进制数组成。这个数字描述了相应的正方形的状态。
0 vacant square 1 block 2 start position 3 goal position
The dataset for Fig. D-1 is as follows:
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
Output
对于每个数据集，打印一行有一个十进制整数，表示从开始到目标的路线的最小移动数。如果没有这样的路由，则输出- 1。每行不应该有除这个数字以外的任何字符。
Sample Input
2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
0 0
Sample Output
1
4
-1
4
10
-1
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N = ;
const int INF = <<;
int board[MAX_N][MAX_N];
/*四个方向*/
int dx[] = {,-,,};
int dy[] = {,,,-};
int w,h,bx,by,ex,ey,mintimes;
void solve(int row ,int col,int count)
{
if(count == && board[row][col] != ) //移动次数超10次并且没有到达终点
return ;
else if(board[row][col] == ) //到达终点位置
{
mintimes = min(mintimes,count); //找最小的移动次数
return;
}
for(int i = ; i < ; i++)
{
int ny = row + dy[i];
int nx = col + dx[i];
if(nx >= && ny >= && nx < w && ny < h) //确定冰壶在网格内
{
if(board[ny][nx] == ) continue; //遇到石块
while(nx >= && ny >= && nx < w && ny < h && board[ny][nx] != &&board[ny][nx] != )
{
ny += dy[i];
nx += dx[i];
}
if(nx < || nx >= w || ny < || ny >= h) continue; //飞出冰盘
int temp = board[ny][nx];
int x = nx,y = ny;
if(board[ny][nx] == )
{
board[ny][nx] = ;
ny -= dy[i];
nx -= dx[i];
}
solve(ny,nx,count+);
board[y][x] = temp; //回复原来状态 }
}
}
int main()
{
while(cin>>w>>h,w||h)
{
for(int i =; i < h;i++)
for(int j = ; j < w;j++)
{
scanf("%d",&board[i][j]);
/*标记开始位置和结束位置*/
if(board[i][j] == )
{
bx = j;
by = i;
}else if(board[i][j] == ){
ex = j;
ey = i;
}
}
mintimes = INF;
solve(by,bx,);
if(mintimes == INF)
cout<<"-1"<<endl;
else
cout<<mintimes<<endl; }
return ;
}