poj 3009 Curling 2.0(dfs)

http://poj.org/problem?id=3009
1匹のカーリングがn*mの格子の上で動いて、0は空き地を代表して、1は石を代表して、2は起点(歩くことができます)、3は終点(歩くことができません)を代表します.
カーリングは運動中、石1またはゴール3に遭遇するまで1つの方向に移動します.3に出会ったら、ゴールまで移動しません.1に遭遇すると、現在の位置に止まり(石の位置に代わるものではないことに注意)、石の位置が1から0に変わり、カーリングが方向を変えて移動し続けます.
また、カーリングが境界まで歩いても石やゴールに出会わなければ、この道はできません.
カーリングの2から3までの最小ステップ数を聞いて、ステップ数の計算方法はカーリングの運動中の方向の変化回数です.
考え方:カーリングは方向を変えるたびに地図の状態が変化するので、bfsは通じません.だからdfsしかできなくて、すべての方案をすべて求めて、それから比較して最小のステップ数を求めます.一歩ずつ歩くたびに、次の格子が実行可能かどうかを判断し、方向を変えるには、ステップ数を1増やして現在の方向dfsで、方向が変わらなければ元の方向dfsで、ステップ数は変わらない.
枝切り:ステップ数が10ステップより大きい場合、TLEを防ぐために検索する必要はありません.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
#define eps 1e-8

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 22;
int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int n,m;
int Map[maxn][maxn];
int sx,sy,ex,ey;
int ans;

void dfs(int x, int y, int d, int step)
{
	if(step > 10)
		return;
	if(Map[x][y] == -1 || Map[x][y] == 1)
		return;
	if(x == ex && y == ey)
	{
		if(ans == -1 || ans > step)
			ans = step;
		return;
	}

	if(Map[x+dir[d][0]][y+dir[d][1]] != 1)
	{
		dfs(x+dir[d][0],y+dir[d][1],d,step);
		return;
	}
	if(Map[x+dir[d][0]][y+dir[d][1]] == 1)
	{
		Map[x+dir[d][0]][y+dir[d][1]] = 0;
		for(int i = 0; i < 4; i++)
		{
			int xx = x + dir[i][0];
			int yy = y + dir[i][1];
			dfs(xx,yy,i,step+1);
		}
		Map[x+dir[d][0]][y+dir[d][1]] = 1;
	}
}

int main()
{
	while(~scanf("%d %d",&m,&n))
	{
		if(n == 0 && m == 0) break;
		memset(Map,-1,sizeof(Map));
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= m; j++)
			{
				scanf("%d",&Map[i][j]);
				if(Map[i][j] == 2)
				{
					sx = i;
					sy = j;
				}
				if(Map[i][j] == 3)
				{
					ex = i;
					ey = j;
				}
			}
		}

		int tx,ty;
		ans = -1;

		for(int d = 0; d < 4; d++)
		{
			tx = sx + dir[d][0];
			ty = sy + dir[d][1];
			if(Map[tx][ty] != -1 && Map[tx][ty] != 1)
				dfs(tx,ty,d,1);
		}
		printf("%d
",ans);
	}
	return 0;
}