2006dd1.c

#include <iostream>

using namespace std; // おまじない

// NO:何も無い OB：障害物 ST：スタート GL：ゴール 
#define NO 0
#define OB 1
#define ST 2
#define GL 3 

int w,h,sx,sy;
int m[20][20];

int search(int m[20][20], int step, int xx, int yy)
{
	static int dx[4]={ 0, 1, 0,-1};
	static int dy[4]={-1, 0, 1, 0};
	int step2=9999;
	
	if(step>10){ // 10回でおしまい
		return step;
	}
	// 上下左右方向に滑らせる
	for(int i=0; i<4; i++){
		int x=xx, y=yy; // 外に出た場合元に戻すため
		if(m[x+dx[i]][y+dy[i]]!=OB){ //障害物じゃない時
			while(true){
				// 盤外に出た
				if(x+dx[i]<0 || x+dx[i]>=w || y+dy[i]<0 || y+dy[i]>=h){
					break;
				}
				// ゴールの上に来た
				if(m[x+dx[i]][y+dy[i]]==GL){
					return step;
				}
				// 障害物にぶつかった
				if(m[x+dx[i]][y+dy[i]]==OB){
					// 障害物を消し、次のターン(再帰)
					m[x+dx[i]][y+dy[i]]=NO;
					int tmp=search(m, step+1, x, y);
					if(step2>tmp){
						step2=tmp;
					}
					m[x+dx[i]][y+dy[i]]=OB;
					break;
				}
				x+=dx[i];
				y+=dy[i];
			}
		}
	}
	return step2;
}

main()
{
	int step;
	
	while(true){
		cin >> w >> h;
		if(w==0 && h==0) break;
		
		for(int j=0; j<h; j++){
			for(int i=0; i<w; i++){
				cin >> m[i][j];
				if(m[i][j]==ST){
					sx=i;
					sy=j;
					m[i][j]=NO;
				}
			}
		}
		step=search(m, 1, sx, sy);
		if(step>10){
			cout << -1 << endl;
		}else{
			cout << step << endl;
		}
	}
	return 0;
}