hdu - 1010 - Tempter of the Bone (二)

#include
#include
#include
#include

using namespace std;

const int maxn = 7 + 10;
int dx[] = {-1, 1, 0, 0};
int dy[] = { 0, 0, -1, 1};
char MAP[maxn][maxn];
bool ok, vis[maxn][maxn];
int N, M, T, Dx, Dy;

void dfs(int x, int y, int cur)
{
if(ok) return;
if(cur == T)
{
if(x == Dx && y == Dy)
{
ok = 1;
return;
}
else
return;
}
int temp = T - cur - (Dx - x) - (Dy - y);
if(temp < 0 || (temp&1)) return;
for(int i = 0; i < 4; i++)
{
int newx = x + dx[i];
int newy = y + dy[i];
if(newx >= 0 && newx < N && newy >= 0 && newy < M && MAP[newx][newy] != 'X' && !vis[newx][newy])
{
vis[newx][newy] = 1;
dfs(newx, newy, cur+1);
vis[newx][newy] = 0;
}
}
}

int main()
{
int Sx, Sy, i, j;
while(scanf("%d%d%d", &N, &M, &T) == 3)
{
if(!N && !M && !T) return 0;
for(i = 0; i < N; i++)
{
for(j = 0; j < M; j++)
{
cin>>MAP[i][j];
if(MAP[i][j] == 'S')
{
Sx = i;
Sy = j;
}
else if(MAP[i][j] == 'D')
{
Dx = i;
Dy = j;
}
}
}
ok = 0;
memset(vis, 0, sizeof(vis));
vis[Sx][Sy] = 1;
dfs(Sx, Sy, 0);
if(ok)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}