http://acm.hdu.edu.cn/showproblem.php?pid=1010
奇偶剪枝：
可以把map看成这样：
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
从为 0 的格子走一步，必然走向为 1 的格子
从为 1 的格子走一步，必然走向为 0 的格子
即：
0 ->1或1->0 必然是奇数步
0->0 走1->1 必然是偶数步
结论：
所以当遇到从 0 走向 0 但是要求时间是奇数的，或者， 从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达！
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define N 10 char maps[N][N];
int dir[][] = {{, }, {, }, {-, }, {, -}};
int m, n, t, sx, sy, ex, ey, f; void DFS(int x, int y , int d)
{
int i, a, b, p, q;
if(x < || x >= m || y < || y >= n)
return ;
if(x == ex && y == ey && d == t)f = ;
if(f == )
return ;
p = t - d;
q = abs(x - ex) + abs(y - ey);
if(p < q || (p % == && q % != ) || (p % != && q % == ))return ;
for(i = ; i < ; i++)
{
a = x + dir[i][];
b = y + dir[i][];
if(a >= && a < m && b >= && b < n && maps[a][b] != 'X')
{
maps[a][b] = 'X';
DFS(a, b, d + );
maps[a][b] = '.';
}
}
return ;
}
int main()
{
int i, j, wall;
while(scanf("%d%d%d", &m, &n, &t), m != || n != || t != )
{
f = wall = ;
for(i = ; i < m ; i++)
{
scanf(" ");
for(j = ; j < n ; j++)
{
scanf("%c", &maps[i][j]);
if(maps[i][j] == 'S')sx = i, sy = j;
else if(maps[i][j] == 'D')ex = i, ey = j;
else if(maps[i][j] == 'X')wall++;
}
}
if(m * n - wall < t)
{
printf("NO\n");
continue;
}
maps[sx][sy] = 'X';
DFS(sx, sy, );
if(f == )printf("YES\n");
else printf("NO\n");
}
return ;
}