1144-Curling 2.0

考え方
深さ優先探索する。
実装(C++)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int W,H,gx,gy;
int ans;
int MAP[22][22];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(int cnt,int x,int y){
	if(x==gx&&y==gy){
		ans=min(ans,cnt);
		return;
	}
	if(cnt>=10||cnt>=ans)return;
	for(int k=0;k<4;k++){
		if(MAP[x+dx[k]][y+dy[k]]!=1){
			int nx=x,ny=y;
			while(1){
				nx+=dx[k],ny+=dy[k];
				if(MAP[nx][ny]!=0)break;
			}
			if(MAP[nx][ny]==-1)continue;
			if(MAP[nx][ny]==1){
				MAP[nx][ny]=0;
				dfs(cnt+1,nx-dx[k],ny-dy[k]);
				MAP[nx][ny]=1;
			}else if(MAP[nx][ny]==3){
				dfs(cnt+1,nx,ny);
			}
		}
	}
}
int main() {
	for(;;){
		cin>>W>>H;
		if(W==0)break;
		int sx,sy;
		for(int i=0;i<22;i++)for(int j=0;j<22;j++)
			MAP[i][j]=-1;
		for(int i=1;i<=H;i++){
			for(int j=1;j<=W;j++){
				cin>>MAP[j][i];
				if(MAP[j][i]==2){
					MAP[j][i]=0;
					sx=j,sy=i;
				}else if(MAP[j][i]==3){
					gx=j,gy=i;
				}
			}
		}
		ans=99999;
		dfs(0,sx,sy);
		if(ans==99999)ans=-1;
		cout<<ans<<endl;
	}
	return 0;
}