//典型的搜索題，這里采用深度優先搜索
//1.本題如果不注意剪枝很容易超時，這里有兩處剪枝
//2.深度搜索時主要是處理：1.具體題目中如何定深度，本題以某一個合法位置的四個方向是同一深度所以for 循環中steps + 1
// 2.理解回溯的思想
//HDU 1010
#include <stdio.h>
#include <stdlib.h>
int dir[4][2] = 
{{0, 1}, {-1, 0}, {0, -1},{1, 0}};
char block[9][9]; //迷宮數組
int si, sj; //入口
int di, dj; //出口
int m, n, t;
int steps;
bool escape;
int DFS (int curx, int cury, int steps)
{
//printf ("%d %d", curx, cury);
if (curx < 0 || curx == 0 || cury < 0 || cury == 0 || curx > m || cury > n) //該路徑位置不合理，此次遞歸結束，但并不是整個遞歸結束
return 0;
if (curx == di && cury == dj && steps == t)
escape = 1;
//奇偶性剪枝
int temp = 0;
temp = (t - steps ) - abs (di - curx) - abs (dj - cury); //處在該位置的深搜是否有可能到達終點
if (temp < 0 || temp & 1) //當temp為奇數時 按位與是 1 ，temp為偶數時 按位是 0
return 0;
if (escape)
return 1;
for (int i = 0; i < 4; i ++)
{
if (block[curx + dir[i][0]][cury + dir[i][1]] != 'X') //因為也可以是D
{
block[curx + dir[i][0]][cury + dir[i][1]] = 'X';
DFS (curx + dir[i][0], cury + dir[i][1], steps + 1);
block[curx + dir[i][0]][cury + dir[i][1]] = '.';
}
}
}
int main ()
{
while ( scanf ("%d%d%d", &m, &n, &t) && (m != 0 && n != 0 && t != 0))
{
getchar ();
int wall = 0;
for (int i = 1; i <= m; i ++)
{
for (int j = 1; j <= n; j ++)
{
scanf ("%c", &block[i][j]);
if (block[i][j] == 'S') //入口坐標
{
si = i;
sj = j;
}
if (block[i][j] == 'D') //出口坐標
{
di = i;
dj = j;
}
if (block[i][j] == 'X')
{
wall ++;
}
}
getchar (); //錯點
}
//printf ("%d %d", si, sj);
/**//*for (int i = 1; i <= m; i ++)
{
for (int j = 1; j <= n; j ++)
{
printf ("%d", block[i][j]);
}
}*/
if ( m * n - wall < t) //剪枝
{
printf ("NO\n");
continue;
}
escape = 0;
steps = 0;
block[si][sj] = 'X';
DFS (si, sj, steps);
if (escape)
printf ("YES\n");
else
printf ("NO\n");
}
system ("pause");
return 0;
}
posted on 2010-08-19 11:20
雪黛依夢 閱讀(505)
評論(0) 編輯 收藏 引用