学步园

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
char z[7][7];
int mark[7][7];
int si,sj,di,dj;
int n,m,t,ok;
int dir[4][2]= {{1,0},{0,1},{0,-1},{-1,0}};
void dfs(int x,int y,int step)
{
    if(ok==1)
        return ;
    if(step==t)
    {
        if(x==di&&y==dj)
            ok=1;
        return ;
    }
    if(abs(dj-y)+abs(di-x)>t-step)
        return ;
    if((abs(di-x)+abs(dj-y))%2!=(t-step)%2)
        return ;
    for(int c=0; c<4; c++)
    {
        int x1=x+dir[c][0];
        int y1=y+dir[c][1];
        if(x1>=0&&x1<n&&y1>=0&&y1<m&&mark[x1][y1]==0&&z[x1][y1]!='X')
        {
            mark[x1][y1]=1;
            dfs(x1,y1,step+1);
            mark[x1][y1]=0;
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&t),n|m|t)
    {
        //getchar();
        int wall=0;
        for(int a=0; a<n; a++)
        {
            for(int b=0; b<m; b++)
            {
                cin>>z[a][b];
                //scanf("%c",&z[a][b]);
                if(z[a][b]=='S')
                {
                    si=a;
                    sj=b;
                }
                else if(z[a][b]=='D')
                {
                    di=a;
                    dj=b;
                }
                else if(z[a][b]=='X')
                    wall++;
                mark[a][b]=0;
            }
            //getchar();
        }

        if(m*n-wall-1<t)
        {
            printf("NO\n");
            continue;
        }
        ok=0;
        mark[si][sj]=1;
        dfs(si,sj,0);
        if(ok==1)printf("YES\n");
        else printf("NO\n");

    }

}

//源代码
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;

char g[7][7];
bool mark[7][7];//标记是否可以访问，0代表可以访问，1代表是墙或者已经访问过了，
              //其实这个数组可以省略，直接用墙X来标记不能访问也可以，用.标记可以访问
int dir[4][2]={-1,0,0,1,1,0,0,-1}; //上下左右四个方向走
int si,sj,di,dj;//起始点坐标和门的坐标
int m,n,t; //由于dfs要用到这些变量，所以不能放在main函数定义
int ok;//标记是否能够完成任务
void dfs(int x,int y,int step)
{
    if(ok==1)  //如果已经找到了，那么不用再继续找了，不要觉得这是多余的，
    return;      //如果已经找到了，但是你仍然要进行很多DFS，如果没有这条
              //语句，又要进行很多冤枉的运算了
    if(step==t) //如果步数达到了t了，那么就么就要结束了
    {
        if(x==di&&y==dj)  //如果此时到了门了，那么就成功了
            ok=1;
        return ;         //不管你是否成功，到了t都要结束了，所以那两个if语句不能写在一起
    }
    if(abs(di-x)+abs(dj-y)>t-step)  //如果直接走到门需要的都比剩下能走的步数大，那么肯定到不了了
        return;

    if((abs(di-x)+abs(dj-y))%2!=(t-step)%2)
        return ;
    for(int i=0;i<4;i++)
    {
        int x1=x+dir[i][0];
        int y1=y+dir[i][1];
        if(x1>=1&&x1<=n&&y1>=1&&y1<=m&&mark[x1][y1]==0&&g[x1][y1]!='X')
        {
            mark[x1][y1]=1;        //回溯思想，标记不能访问了
            dfs(x1,y1,step+1);     //步数+1，递归进行深搜
            mark[x1][y1]=0;        //但是要记得改回来，这是个for循环，临时的状态修改了要恢复原状
        }
    }
}
int main()
{
    for(;cin>>n>>m>>t&&(m||n||t);)
    {
        int wall=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>g[i][j];
                if(g[i][j]=='S')
                {
                    si=i;
                    sj=j;
                }
                else if(g[i][j]=='D')
                {
                    di=i;
                    dj=j;
                }
                else if(g[i][j]=='X')
                {
                    wall++;
                }
                mark[i][j]=0;
            }
            if(n*m-wall-1<t)     //如果说所有的可以走的路加起来都比要求的时间小的话，那么肯定到不了了
            {
                cout<<"NO"<<endl;
                continue;
            }
            ok=0;
            mark[si][sj]=1;      //标记下起点不能访问了
            dfs(si,sj,0);        //进行深度搜索
            cout<<(ok?"YES":"NO")<<endl;
    }
}