题意：从开始位置走到结束位置，恰好走 t 步 YES

否则 NO

搜索题，由于是恰好走到，所以用到了奇偶剪枝

什么是奇偶剪枝，我也是刚知道

所给步数为 t ，起始位置坐标 (begin_x,begin_y), 结束位置坐标 (end_x,end_y)

两位置最短距离为 ju = abs(end_x - begin_x) + abs(end_y - begin_y)

若 t - ju 为奇数，则无论如何不能恰好走到

为偶数才有可能恰好走到

代码中 pos + dis 即 ju

代码如下：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int m,n,t;char map[8][8];int vis[8][8];int flag;int begin_x,begin_y,end_x,end_y;int p[][2] = {
    {-1,0},{
    0,1},{
    1,0},{
    0,-1}};  //偏移量：上，下，左，右void dfs(int x,int y,int pos)             //pos 为当前已走步数{    if(flag) return ;                  //剪枝：已经到达目的地    if(pos > t) return ;               //剪枝：步数超过 t    if(x == end_x && y == end_y && pos == t)  //恰好 t 步走到    {        flag = 1;        return ;    }    int dis = abs(end_x - x) + abs(end_y - y);  //当前位置到结束位置的最短距离    if((t - dis - pos) % 2 != 0) return;       //奇偶剪枝，很重要，不剪TLE    for(int i = 0; i < 4; i ++)         //搜索四个方向    {        int tx = x + p[i][0];        int ty = y + p[i][1];        if(tx >= 0 && tx < m && ty >= 0 && ty < n && !vis[tx][ty] && map[tx][ty] != 'X')        {            vis[tx][ty] = 1;            dfs(tx,ty,pos + 1);            vis[tx][ty] = 0;        }    }}int main(){    while(~scanf("%d%d%d",&m,&n,&t) && (m || n || t))    {        memset(vis,0,sizeof(vis));        flag = 0;        int k = 0;        for(int i = 0; i < m; i ++)        {            for(int j = 0 ; j < n; j++)            {                cin>>map[i][j];             //scanf注意回车                if(map[i][j] == 'S')                {                    begin_x = i;                    begin_y = j;                    vis[i][j] = 1;                }                if(map[i][j] == 'D')                {                    end_x = i;                    end_y = j;                }                if(map[i][j] == 'X')                    k ++;            }        }        if((m * n - k) > t) dfs(begin_x,begin_y,0);        if(flag) printf("YES\n");        else printf("NO\n");    }    return 0;}