[数据结构与算法]【HDU 1010】Tempter of the Bone:DFS + 奇偶剪枝

传送门

题意

从$s$出发，初始时间为$0$， 只有在第$t$秒，$D$会开门，判断能否走出迷宫。

分析

这里我们如果去写朴素的$DFS$的话，很容易会被$tle$的，因为这题要考虑的不仅仅是能够逃出迷宫，还得保证在规定的时间节点上走出迷宫，这无疑是增加了一个纬度，所以我们需要去进行剪枝
怎么剪枝呢，首先是可行性剪枝，在一个方格图中，如果不考虑障碍的问题的话，那么两个点之间的最短路径长度就是他们的曼哈顿距离，所以，如果起点和终点的曼哈顿距离大于给定的时间的话，那么必然是走不到终点的
再有就是去进行奇偶剪枝，因为我从起点到终点，我们首先选定一条路，因为中间有障碍物的存在，所以我们必须不断地去更改我们的路线，但因为我们最终的目标是不变的，所以，我们每往上走一格，相对应的就要往下走一格去修正我的路线，所以每次需要走两步来进行修正，所以和最短的曼哈顿的距离应该是同奇偶的，所以可以根据这个性质进行一个剪枝

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 100;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {return (b > 0) ? gcd(b, a % b) : a;}
int n,m,k;
char str[N][N];
bool st[N][N];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int sx,sy,ex,ey;
bool flag;

void dfs(int x,int y,int t){
    // cout << x << ' '  << y << ' ' << t << endl;
    if(str[x][y] == 'D' && (t == k)){
        flag = true;
        return;
    }
    if(flag) return;
    st[x][y] = true;
    for(int i = 0;i < 4;i++){
        int a = x + dx[i],b = y + dy[i];
        if(a < 1 || a > n || b < 1 || b > m) continue;
        if(st[a][b]) continue;
        if(str[a][b] == 'X') continue;
        int p = abs(ex - a) + abs(ey - b);
        if(p + t + 1 > k) continue;
        if((p + t + 1) % 2 != k % 2) continue;
        st[a][b] = true; 
        dfs(a,b,t + 1);
        st[a][b] = false;

    }
    st[x][y] = false;
}

int main() {
    while(1){
        read(n),read(m),read(k);
        if(n == 0 && m == 0 && k == 0) break;
        for(int i = 1;i <= n;i++) scanf("%s",str[i] + 1);
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= m;j++){
                st[i][j] = false;
                if(str[i][j] == 'S') sx = i,sy = j;
                if(str[i][j] == 'D') ex = i,ey = j;
            }
        flag = false;
        int t = abs(ex - sx) + (ey - sy);
        if(t > k || t % 2 != k % 2) {
            puts("NO");
            continue;
        }
        st[sx][sy] = true;
        dfs(sx,sy,0);
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/