题意：输入一个n*m的迷宫，和一个T：可以在迷宫中生存的最大时间。S为起点，D为终点。并且，每个格子只能踩一次，且只能维持一秒，然后该块地板就会塌陷。所以你必须每秒走一步，且到D点时，所用时间为T。用深搜。
奇偶性剪枝：如果当前的狗所在的坐标与D的坐标奇偶性不一样，那么狗需要走奇数步。
同理，如果狗所在坐标与D的坐标奇偶性一样，那么狗需要走偶数步数。
也就是说，狗的坐标x、y和对2取余是它的奇偶性，Dxy和对2取余是D的奇偶性。
两个奇偶性一加再对2取余，拿这个余数去与剩下时间对2取余的余数作比较即可。
Sample Input
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
Sample Output
NO
YES
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
#include <queue> using namespace std; int m,n,t;
char map[][];
int dir[][]={{,},{-,},{,-},{,}};
int ex,ey,sx,sy,ok;//e表示end，终点，s表示start，出发点，ok用来判断是否在规定时间到达 void dfs(int x,int y,int cnt)
{
int i;
if(cnt==t)//剪枝：到时间了符合条件ok=1再退出，不符合条件直接退出。
{
if(ex==x&&ey==y)ok=;
return;
}
if(ok)return;//找到解后还有部分在继续搜索，这条是为了让其它搜索停止 for(i=;i<;i++)
{
int fx=x+dir[i][];
int fy=y+dir[i][];
if(fx>=&&fx<n&&fy>=&&fy<m&&map[fx][fy]!='X')
{
map[fx][fy]='X';
dfs(fx,fy,cnt+);
map[fx][fy]='.'; //回溯
}
}
}
int main()
{
int i,j;
//freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&n,&m,&t))
{
if (m == && n == & t == )
break ; for(i=;i<n;i++)
{
scanf("%s",map[i]);
for(j=;map[i][j]!='\0';j++)
{
if(map[i][j]=='S')
{
sx=i;sy=j;
}
else if(map[i][j]=='D')
{
ex=i;ey=j;
} }
}
if(abs(sx - ex) + abs(sy - ey) > t || (sx +sy+ex+ey+t)% == )//如果步数大于时间 或步数的奇偶性不一致
printf("NO\n");
else
{
ok=;
map[sx][sy]='X';
dfs(sx,sy,);
if(ok)printf("YES\n");
else printf("NO\n");
}
}
return ;
}