大佬的题解链接，给我提供了很大的帮助
https://www.cppblog.com/Geek/archive/2010/04/26/113615.html

原题如下
小狗在一个古老的迷宫中发现了一根骨头，这让他非常着迷。然而，当他捡起它时，迷宫开始摇晃，小狗能感觉到地面在下沉。他意识到这块骨头是一个陷阱，他拼命地试图走出这个迷宫。

迷宫是一个矩形，大小为 N x M。迷宫里有一扇门。一开始，门是关闭的，它会在第 T 秒打开一小段时间（不到 1 秒）。因此，小狗必须在 T 秒到达门口。在每一秒钟内，他都可以将一个方块移动到上、下、左、右相邻的方块之一。一旦他进入一个方块，这个方块的地面就会开始下沉，并在下一秒消失。他不能在一个街区停留超过一秒钟，也不能进入一个被访问过的街区。可怜的小狗能活下来吗？请帮助他。

输入
输入由多个测试用例组成。每个测试用例的第一行包含三个整数 N、M 和 T（1 < N、M < 7;0 < T < 50），分别表示迷宫的大小和门打开的时间。接下来的 N 行给出迷宫布局，每行包含 M 个字符。角色是以下角色之一：“

X”：一堵墙，小狗无法进入;
“S”：小狗的起点;
“D”：门;or
‘.’：一个空块。

输入以三个 0 终止。不处理此测试用例。

输出
对于每个测试用例，如果小狗可以存活，则在一行中打印“YES”，否则打印“NO”。

示例输入
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
…D
0 0 0

示例输出
NO
YES

（鄙人的事后诸葛亮）

由于是要求在规定的时间到达规定的地点，所以bfs不适用，使用dfs

难点一
奇偶性剪枝

把map看作奇偶相间的格子

0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1

0 ——> 1 1 ——> 0 无论咋走都是奇数步
0 ——> 0 1 ——> 1 咋走都是偶数步

设起点为si sj 终点为di dj
如果abs(si - sj) + abs(di - dj)为奇数，则说明abs(si - sj)与abs(di - dj)奇偶性不同，就要走奇数步
如果abs(si - sj) + abs(di - dj)为偶数，则说明abs(si - sj)与abs(di - dj)奇偶性相同，就要走偶数步

如果起点跟终点坐标的奇偶性确定了，那么所需要的步数为奇数还是为偶数就确定了！！

那么(t - cnt) 与 abs(si - sj) + abs(di - dj) 的奇偶性必须相同，因为题意要求必须在规定的时间到规定的地点

所以(t - cnt) - abs(di - si) - abs(dj - sj)必须为偶数！！（这样奇偶性才相同），才有可能在规定时间到达规定地点（为啥这个公式跟上个公式不一样应该是奇偶性的某个性质推导出来的，但是我没找到原理，如果有佬知道，还望不吝赐教）

难点二
为啥n*m - w（地图中非障碍物的方块数）不能等于给定的的时间

因为起点也包含在其中，按照一步一秒的逻辑，他俩相等时，合法路线恰好是曼哈顿距离时，会因为给定的时间多一秒而错过 （但是为啥不能在第一秒结束前的那一刻，小狗再从起点跳到下一个格子呢，这样就能刚好相等了）<——这是我迄今还未完全理解的一个点，同样还望佬们不吝赐教！（抱拳感谢）

#include <iostream>
#include <math.h>
using namespace std;
const int N = 10;
char g[N][N];//记得用字符串定义
int si, sj, di, dj;//定义起点跟终点的坐标
int n, m, t;
bool a;//定义一个bool类型用来判断是否符合输出条件
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//偏移量

//输入函数的起点坐标跟当前花费的时间
void dfs(int si, int sj, int cnt)
{
    //先处理不需要递归的特殊情况（一般是结束递归的情况）
    if(si < 0 || si >= n || sj < 0 || sj >= m)  return;//坐标越界
    if(si == di && sj == dj && cnt == t)//符合输出条件
    {
        a = 1;
        return;
    }

    int temp = t - cnt - abs(si - di) - abs(sj - dj);
    if(temp < 0)  return;//剪枝——时间不够的情况（可能绕路了）
    //处理一般情况（需要递归）  枚举每一种可能，在每一种可能里面递归
    for(int i = 0; i < 4; i ++)
    {
        int x = si + dx[i], y = sj + dy[i];
        if(g[x][y] != 'X')
        {
            g[x][y] = 'X';//标记  防止返回
            dfs(x, y, cnt + 1);
            g[x][y] = '.';//回溯
        }
    }
    return;//记得返回
}

int main()
{
    //因为多个样例，所以循环输入
    while(cin >> n >> m >> t)
    {
        if(n == 0 && m == 0 && t == 0)  break;//结束标志

        int w = 0;//一定记得初始化
        for(int i = 0; i < n; i ++)
        {
            for(int j = 0; j < m; j ++)
            {
                cin >> g[i][j];
                if(g[i][j] == 'S')  si = i, sj = j;//记录起始坐标

                if(g[i][j] == 'D')  di = i, dj = j;//记录终止坐标

                if(g[i][j] == 'X')  w ++;//记录障碍物的数量
            }
        }
        //剪枝——时间过剩的情况
        //剩余能用于停留的方块必须大于给定的时间
        //不能的等于的原因是起点也在其中，除去起点能移动的步数就小于时间了
        if(n * m - w <= t)
        {
            cout << "NO" << endl;
            continue;
        }
        //奇偶性剪枝
        int f = t - abs(di - si)- abs(dj - sj);
        if(f % 2 == 1)
        {
            cout << "NO" << endl;
            continue;
        }
        //起点做标记，防止返回
        a = 0;  g[si][sj] = 'X';
        dfs(si, sj, 0);

        if(a)  cout << "YES" << endl;
        else  cout << "NO" << endl;
    }

    return 0;
}