题目：
Problem Description
迷宫是一个大小为N×M的矩形。迷宫里有一扇门。一开始，门是关着的，它会在第T秒打开一小段时间（不到1秒）。因此，小狗必须正好在第T秒到达门口。在每一秒钟里，他都可以移动到上、下、左、右相邻区域。一旦他进入一个区域，这个区域的地面就会开始下沉，并在下一秒消失。他不能在一个区域停留超过一秒钟，也不能进入一个已经访问过的区域。可怜的小狗能活下来吗？请帮帮他。
Input
输入由多个测试用例组成。每个测试用例的第一行包含三个整数N、M和T（1<N、M<7；0<T<50），分别表示迷宫的大小和门打开的时间。接下来的N行给出了迷宫布局，每行包含M个字符。字符是下列字符之一：
“X”：一堵墙，小狗不能进去；
“S”：狗的起点；
“D”：门；
“.”：空区域。
Output
对于每组测试数据，如果狗能活下来输出YES，活不下来输出NO。
Sample Input
4 4 5
S.X.
…X.
…XD
…
3 4 5
S.X.
…X.
…D
0 0 0
Sample Output
NO
YES
解答过程分析：
确定题目类型：
迷宫问题是典型DFS的题目，用来寻找路径，这里还需要进行对时间的判断。
DFS模板框架：
function dfs(当前状态){
if(当前状态 == 目的状态){
···}for(···寻找新状态){
if(状态合法){
vis[访问该点]；dfs(新状态);?是否需要恢复现场->vis[恢复访问]} }if(找不到新状态){
···}
}初步思路：
我们的目标状态为 在第T秒时可以恰好到达目标点，其中包含了两个条件：
1.可成功到达目标点
2.到达时刻恰为T
所以一开始我先确定了目标状态,写了一个初步的代码
#include<iostream>
#include<cstring>
using namespace std;
int R,C;
int h,l,x,y;
int pd;
int d;
int t;
char s;
bool f[10][10];
int ch[4]={
-1,1,0,0},
cl[4]={
0,0,-1,1};
void dfs(int u,int v){
if(t==d&&u==x&&v==y){
pd=1;}for(int i=0;i<4;i++){
int hh=u+ch[i];int ll=v+cl[i];if(f[hh][ll]==0&&hh>=1&&hh<=R&&ll>=1&&ll<=C&&!pd){
t++;f[hh][ll]=1;dfs(hh,ll);f[hh][ll]=0;t--;}}
}
int main(){
while(cin>>R>>C>>d&&R&&C&&d){
memset(f,0,sizeof(f));pd=0;t=0;for(int i=1;i<=R;i++){
for(int j=1;j<=C;j++){
cin>>s;if(s=='S')h=i,l=j;else if(s=='D')x=i,y=j;else if(s=='X')f[i][j]=1;}getchar();}dfs(h,l);if(pd==1) cout<<"YES"<<endl;else cout<<"NO"<<endl;}}
原因分析：
但显而易见，对于这道题来说，这么粗糙的写法，没有经过丝毫优化，只会换来超时的惨痛教训，所以我们还要进行一系列减枝优化
首先要总结哪些情况是我们需要减去的。
时间角度：
1.当时间超过了要求时，之后不论如何都是无用功。
2.当到达目标点时，时间小于目标要求（大于的情况已经被排除），之后也不必讨论。
路径角度：
我们需要引入一个奇偶减枝的方法
以大写的X，Y代表一个点的坐标，以小写的x,y代表另一个点的坐标，那么abs(X-x)+abs(Y-y)就是两点间的最小路径，记作Minlen，
对于从（x,y）出发试图到达(X,Y)的任意路径，其路径记作Len，
它们存在关系：
Minlen%2==Len%2,即奇偶性相同
若所给路径大小与Minlen不同，则说明该路径不可行，
而上述解答中的（t-d）就代表所给点到目标点的剩余步数，若（t-d）与Minlen连奇偶性都不同，则同样不必讨论。
解决方案：
#include<bits/stdc++.h>
using namespace std;
int R,C,d;//行，列，时间
int h,l,x,y;//起点终点坐标
int pd;//结果
int t;//该状态下的时间
char f[10][10];
int ch[4]={
-1,1,0,0},
cl[4]={
0,0,-1,1};
void dfs(int u,int v){
if(t>d)return;//超时则不再可能 if ((abs(x - u) + abs(y - v)) % 2 != (d - t) % 2)return;for(int i=0;i<4;i++){
int hh=u+ch[i];int ll=v+cl[i];if(hh==x&&ll==y&&t+1==d){
//为了避免耗费内存，先一步判断 pd=1;return;}if(hh==x&&ll==y&&t+1!=d)continue;//可不必再继续这一步 if(f[hh][ll]!='X'&&hh>=0&&hh<R&&ll>=0&&ll<C&&pd==0){
t++;f[hh][ll]='X';dfs(hh,ll);f[hh][ll]='.';t--;//注意恢复原来的状态 }}
}
int main(){
while(cin>>R>>C>>d){
if(R==0&&C==0&&d==0)break;pd=t=0;for(int i=0;i<R;i++){
for(int j=0;j<C;j++){
cin>>f[i][j];if(f[i][j]=='S')h=i,l=j,f[i][j]='X';else if(f[i][j]=='D')x=i,y=j;}}dfs(h,l);if(pd==1) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
}