//典型的搜索题，这里采用深度优先搜索
//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
雪黛依梦 阅读(485)
评论(0) 编辑 收藏 引用