在行星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
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int MAX_N = 25; 5 const int INF = 1<<30; 6 int board[MAX_N][MAX_N]; 7 /*四个方向*/ 8 int dx[] = {1,-1,0,0}; 9 int dy[] = {0,0,1,-1}; 10 int w,h,bx,by,ex,ey,mintimes; 11 void solve(int row ,int col,int count) 12 { 13 if(count == 10 && board[row][col] != 3) //移动次数超10次并且没有到达终点 14 return ; 15 else if(board[row][col] == 3) //到达终点位置 16 { 17 mintimes = min(mintimes,count); //找最小的移动次数 18 return; 19 } 20 for(int i = 0; i < 4; i++) 21 { 22 int ny = row + dy[i]; 23 int nx = col + dx[i]; 24 if(nx >= 0 && ny >= 0 && nx < w && ny < h) //确定冰壶在网格内 25 { 26 if(board[ny][nx] == 1) continue; //遇到石块 27 while(nx >= 0 && ny >= 0 && nx < w && ny < h && board[ny][nx] != 1 &&board[ny][nx] != 3) 28 { 29 ny += dy[i]; 30 nx += dx[i]; 31 } 32 if(nx < 0 || nx >= w || ny < 0|| ny >= h) continue; //飞出冰盘 33 int temp = board[ny][nx]; 34 int x = nx,y = ny; 35 if(board[ny][nx] == 1) 36 { 37 board[ny][nx] = 0; 38 ny -= dy[i]; 39 nx -= dx[i]; 40 } 41 solve(ny,nx,count+1); 42 board[y][x] = temp; //回复原来状态 43 44 } 45 } 46 } 47 int main() 48 { 49 while(cin>>w>>h,w||h) 50 { 51 for(int i =0; i < h;i++) 52 for(int j = 0; j < w;j++) 53 { 54 scanf("%d",&board[i][j]); 55 /*标记开始位置和结束位置*/ 56 if(board[i][j] == 2) 57 { 58 bx = j; 59 by = i; 60 }else if(board[i][j] == 3){ 61 ex = j; 62 ey = i; 63 } 64 } 65 mintimes = INF; 66 solve(by,bx,0); 67 if(mintimes == INF) 68 cout<<"-1"<<endl; 69 else 70 cout<<mintimes<<endl; 71 72 } 73 return 0; 74 }