深度优先搜索奇偶性剪枝

我们先来看一道题目：

有一个n×m 大小的迷宫。其中字符’S’表示起点，字符’D’表示出口，字符’X’表示墙壁，字符’.‘表示平地。你需要从’S’出发走到’D’，每次只能向上下左右相邻的位置移动，并且不能走出地图，也不能走进墙壁。
每次移动消耗 1 时间，走过路都会塌陷，因此不能走回头路或者原地不动。现在已知出口的大门会在 T 时间打开，判断在 0 时间从起点出发能否逃离迷宫。
数据范围 n,m≤10,T≤50。
只有从起点往终点搜，步数恰好等于T时，才能成立。
我们只需要DFS来搜索每条路线，并且只需要搜到T世家就可以了（可行性剪枝）。但是仅仅这样还无法通过本题，还需要更多的剪枝。

如果把迷宫看作一个棋盘，S起点处是白色，那么走偶数步应该是白色。

如上图所示，将n×m的网格染成黑白两色。我们记每个格子的行数和列数的和为x，如果x为偶数，那么格子就是白色，反之奇数就是黑色，容易发现两个相邻的格子颜色肯定不一样，也就是说每走一步颜色都会不一样。更普遍的结论是：走奇数步会改变颜色，走偶数步颜色不变。
那么如果起点和终点颜色不一样，而T是奇数的话，就不可能逃离迷宫。同理，如果起点和终点颜色不一样，而T是偶数和的话，也不能逃离迷宫。遇到这两种情况时，就不用进行DFS了，直接输出“NO”。
这样的剪枝就是奇偶性剪枝，本质上也属于可行性剪枝。
vis标记每个位置是否走过，因为走过的位置会塌陷，不能走多次。
dx和dy数组用来枚举四个方向。
ok标记当前是否已经找到答案，在搜索过程中如果为true就直接return，这也是一种最优性剪枝。
当找到答案时，ok为true时，就直接return（最优性剪枝）
若当前时间等于T，跟证据当前位置是否是出口来更新ok，并直接return。（可行性剪枝）
然后再dfs入口处标记该位置已经被访问过，并在dfs出口处清空标记。
(sx+sy+ex+ey+T)%2!=0是因为设起点是S，T为步数，E为终点，则(S+T)%2==E%2移项后就是，(S+T+E)%2
示例代码：

#include 
using namespace std;
const int N = 10;
int n, m, T;
char mat[N][N];
bool vis[N][N];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
bool ok;
void dfs(int x,int y,int t){
    if(ok)
        return;
    if(t==T){
        if(mat[x][y]=='D')
            ok=true;
        return;
    }
    vis[x][y]=true;
    for(int i=0;i<4;i++){
        int tx=x+dx[i];
        int ty=y+dy[i];
        if(tx<0 || tx>=n || ty<0 || ty>=m || mat[tx][ty]=='X' ||vis[tx][ty])
            continue;
        dfs(tx,ty,t+1);
    }
    vis[x][y]=false;
}
int main() {
    cin >> n >> m >> T;
    for (int i = 0; i < n; ++i) {
        cin >> mat[i];
    }
    int sx,sy,ex,ey;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(mat[i][j]=='S')
                sx=i,sy=j;
            if(mat[i][j]=='D')
                ex=i,ey=j;
        }
    }
    if((sx+sy+ex+ey+T)%2!=0){
        cout<<"NO"<<endl;
    }
    else{
        ok=false;
        dfs(sx,sy,0);
        if(ok)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}