http://acm.hdu.edu.cn/showproblem.php?pid=1010
给出一个n*m的迷宫 X为墙 .为空地 S为起点 D为终点 给出时间T
每走一步花费一单位的时间 走过的空地会消失不能再次经过
问能不能刚好花费T单位时间到达终点（在T时间前到达终点也算失败）
典型深搜 为减少时间花费加点剪枝
1.奇偶剪枝：给出一个01矩阵如下
从0到0或从1到1 必然要经过偶数步 从0到1或从1到0 必然要经过奇数步 所以可以通过比较起点终点的属性 判明是否已经是不可能到达的
2.如果总的地板数 小于（T - 1）个 也不可能到达
# include <stdio.h>
# define MAX 10
# define X x+dir[i][0]
# define Y y+dir[i][1] int n, m, time, sx, sy, ex, ey, dir[4][2] = {{0,-1},{1,0},{0,1},{-1,0}};
char pic[MAX][MAX];
int sign[MAX][MAX];//奇偶矩阵 bool is_ok()//奇偶剪枝
{
if(time % 2 == 0)
{
if(sign[sx][sy] == sign[ex][ey]) return true;
else return false;
}
else
{
if(sign[sx][sy] != sign[ex][ey]) return true;
else return false;
}
} bool in_map(int a, int b)//判断边界
{
return a >= 0 && a < n && b >= 0 && b < m;
} bool dfs(int x, int y, int step)
{
if(x == ex && y == ey)//到达出门 若门刚好打开 返回成功
{
if(step == time) return true;
else return false;
} for(int i = 0; i < 4; i++)//四向拓展
{
if(in_map(X, Y) && pic[X][Y] != 'X')
{
pic[X][Y] = 'X';
if(dfs(X, Y, step + 1)) return true;//若返回的是成功 则说明已找到路 退出
pic[X][Y] = '.';
}
}
return false;
} int main()
{
for(int i = 0; i < MAX; i++)//初始化奇偶矩阵
{
sign[i][0] = i % 2;
for(int j = 1; j < MAX; j++)
sign[i][j] = (sign[i][j - 1] + 1) % 2;
} while(scanf("%d %d %d", &n, &m, &time) && (n || m || time))
{
int groud = 0;//空地计数器
for(int i = 0; i < n; i++)
{
scanf("%s",pic[i]);
for(int j = 0; j < m; j++)
{
if(pic[i][j] == 'S')//起点
sx = i, sy = j, pic[i][j] = 'X';
else if(pic[i][j] == 'D')//终点
ex = i, ey = j, pic[i][j] = '.';
else if(pic[i][j] == '.')
groud++;
}
} if(is_ok() && groud + 1 >= time && dfs(sx, sy, 0)) printf("YES\n");
else printf("NO\n");
} return 0;
}
/*
/*
测试数据：
1 5 4
S...D
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
2 2 1
S.
.D
8 8 7
.DXS...X
........
XX..XX..
.X.X.X.X
..X.....
X....X..
........
XXXX....
5 4 18
S...
....
....
....
...D
6 6 10
S.....
......
......
......
......
.....D
2 3 2
SDX
..X
2 2 3
SD
..
2 2 2
SD
XX
4 4 6
.S..
XXX.
XXX.
XXXD
5 4 8
S...
.XX.
.X..
.X.X
....
3 3 3333
.S.
...
...
2 2 1
SD
..
1 5 4
S...D
4 5 5
.S...
..X..
.XDX.
..X..
2 4 7
SD..
....
2 2 3
S.
D.
4 4 9
S..X
X.X.
..XD
.... 输出：
YES
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
YES
YES
YES
*/