深度优先搜索

基本思想：从初始状态S开始，利用规则生成搜索树下一层任一个结点，检查是否出现目标状态G，若未出现，以此状态利用规则生成再下一层任一个结点，再检查是否为目标节点G，若未出现，继续以上操作过程，一直进行到叶节点（即不能再生成新状态节点），当它仍不是目标状态G时，回溯到上一层结果，取另一可能扩展搜索的分支。生成新状态节点。若仍不是目标状态，就按该分支一直扩展到叶节点，若仍不是目标，采用相同的回溯办法回退到上层节点，扩展可能的分支生成新状态，…，一直进行下去，直到找到目标状态G为止。

#include<iostream>
#include<cmath>
using namespace std;
char Map[9][9];
int n,m,time,di,dj,si,sj;
bool escape;
int dir[4][2]= {{0,-1},{0,1},{1,0},{-1,0}}; //当时看人家答案都没有看懂这句，也算学习了，意思是用一个数组指定了四个方向。

void dfs(int si,int sj,int t)
{
    if(si>n||sj>m||si<=0||sj<=0)//如果搜索过程中，超出边界那么结束这条路径的搜索，返回上个根节点的邻接表的异于这个结点的结点
        return ;
    if(time==t&&si==di&&sj==dj)//如果搜索过程中发现任何一条满足条件的路径，即可标志 存在性
        escape=1;
    if(escape)
        return ;
    int  temp=(time-t)-abs(si-di)-abs(sj-dj);//这个语句 又包含了两个剪枝的地方，其一：如果某条搜索路径到达某结点后距规定时间的剩余时间已经
    if(time-t<0||temp&1)  //小于此节点到终点的最短所需时间，那么也应该和这次搜索说拜拜。其二：就是奇偶性剪枝，注意到同奇或同偶相减结果
        return ;               //为偶数，否则奇数。
    for(int i=0; i<4; i++) // 对于每个根节点四个方向搜索
    {
        if(Map[si+dir[i][0]][sj+dir[i][1]]!='X') //如果此节点可以走
        {
            Map[si+dir[i][0]][sj+dir[i][1]]='X';//且不能一条路径重复某个结点，所以标记已经走过。
            dfs(si+dir[i][0],sj+dir[i][1],t+1);  //然后再以此为根结点，递归调用，同时t+1路径长度加一
            Map[si+dir[i][0]][sj+dir[i][1]]='.';  //每回溯一条边，把结点标记状态收回，不能影响其他路径经过这个点
        }
    }
    return ;
}

int main()
{
    int i,j;
    while(cin>>n>>m>>time,time+m+n)
    {
        int block=0;
        for(i=1; i<=n; i++)
            for(j=1; j<=m; j++)
            {
                cin>>Map[i][j];
                if(Map[i][j]=='X')
                    block++;
                else if(Map[i][j]=='D')
                {
                    di=i;
                    dj=j;
                }
                else if(Map[i][j]=='S')
                {
                    si=i;
                    sj=j;
                }
            }
        if(n*m-block<time)//也是剪枝，就是能走的路压根就小于时间
        {
            cout<<"NO"<<endl;
            continue;
        }
        escape=0;
        Map[si][sj]='X';
        dfs(si,sj,0);
        if(escape)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}