<题目链接>
题目大意：
一个迷宫，给定一个起点和终点，以及一些障碍物，所有的点走过一次后就不能再走(该点会下陷)。现在问你，是否能从起点在时间恰好为t的时候走到终点。
解题分析：
本题恰好要在某一时刻到达，所以需要用到可行性剪枝中的奇偶剪枝，如果在某一点，它所剩的步数与到终点的最短距离之差是偶数，说明这种情况有可能恰好在规定时刻到达终点，否则不可能，将其剪去。
#include <bits/stdc++.h>
using namespace std; char mpa[][];
int vis[][];
int n,m,t,sx,sy,ex,ey;
bool fp;
const int dir[][]={,,,,-,,,-}; void dfs(int x,int y,int step){
if(x==ex&&y==ey&&step==t){fp=true;return;} //恰好达到终点
int tmp=t-step-abs(ex-x)-abs(ey-y); //重要的剪枝，可行性奇偶剪枝
if(tmp< || tmp&)return;
if(step>t)return; //超过规定时间，剪去
if(fp)return;
for(int k=;k<;k++){
int nx=x+dir[k][],ny=y+dir[k][];
if(nx<||nx>n||ny<||ny>m||vis[nx][ny]||mpa[nx][ny]=='X')continue;
vis[nx][ny]=;
dfs(nx,ny,step+);
if(fp)return; //已经找到答案，结束分支
vis[nx][ny]=;
}
}
int main(){
while(~scanf("%d%d%d",&n,&m,&t),n||m||t){
for(int i=;i<=n;i++){
scanf("%s",mpa[i]+);
for(int j=;j<=m;j++){
if(mpa[i][j]=='S')sx=i,sy=j;
if(mpa[i][j]=='D')ex=i,ey=j;
}
}
memset(vis,,sizeof(vis));
fp=false;
vis[sx][sy]=;dfs(sx,sy,);
fp?puts("YES"):puts("NO");
}
}