既然没人同时用DFS和BFS，那我来更新一个两者都用的题解

题目链接

wyh的迷宫

思路（DFS+BFS）

这道题妥妥的搜索模板题

DFS思路与优化

对于每一个节点，先将其打上“已访问（不可达）”的标签，然后查询其周围是否存在可访问节点（即可达但未访问的节点，包括终点），如果存在则深入搜索。

优化注意

一般情况下搜索完退回是需要恢复到初始状态的，但是这里不能恢复，否则会存在一个节点访问多次的情况（比如下图，蓝色格子可能从周围的四个红色格子进入，可能被访问至少4次），从而导致TLE

如果不恢复初始状态，那么每个格子最多被访问1次（访问之后就被标记了，没有机会访问第2次），保证了时间复杂度。因为题目只关心是否可达，不关心距离，所以是否重复访问对最终结果没有任何影响

参考代码：

bool dfs( node begin ){
    ch[begin.fi][begin.se] = 'x';
    for( int i = 0; i < 4; i ++ ){
        int x = begin.fi + bias[i][0], y = begin.se + bias[i][1];
        if( x < 1 || x > n || y < 1 || y > m ) continue;  // 超出边界
        if( ch[x][y] == 'x' ) continue;  // 已经访问或者本身不可达
        if( ch[x][y] == 't' ) return true;  // 找到终点
        if( dfs({x, y}) ) return true;  // 该路径找到终点
    }
    return false;  // 没找到终点
}

BFS思路与优化

维护一个队列，存储所有待访问的节点。对于每一个节点，打上标记后，查询其周围节点可访问节点并将其放入队尾。如果遇到终点，则停止一切查询，直接返回结果

优化注意

访问标记应该在入队后立刻打上。这是防止节点多次入队（比如DFS里面那张图，上方的红色和左侧的红色可能同时入队，此时如果先访问上方的红色，那么蓝色入队；再访问左侧的红色，由于蓝色节点此时未被访问，没有标记，会再次入队），否则会MLE

先打标记后访问不会对结果造成干扰（终点除外，需特判），这是因为打上标记的节点已经通过队列存储起来了

参考代码：

bool bfs( node begin ){
    qe.push(begin);
    while( !qe.empty() ){
        node now = qe.front(); qe.pop();
        for( int i = 0; i < 4; i ++ ){
            int x = now.fi + bias[i][0], y = now.se + bias[i][1];
            if( x < 1 || x > n || y < 1 || y > m ) continue;
            if( ch[x][y] == 'x' ) continue;
			if( ch[x][y] == 't' ) return true;  // 终点应当在入队前进行特判
			qe.push({x, y}); ch[x][y] = 'x';  // 入队就立刻打上标记
        }
    }
    return false;
}

AC code

#include <iostream>
#include <utility>
#include <queue>
#define fi first
#define se second
using namespace std;
using node = pair<int, int>;  // 用于表示节点的坐标

const int N = 500;  // 数据范围
char ch[N+10][N+10];
queue<node> qe;  // bfs用队列
int bias[][2] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1},
};  // 格子的偏差值
int n, m;

// dfs算法
bool dfs( node begin ){
    ch[begin.fi][begin.se] = 'x';
    for( int i = 0; i < 4; i ++ ){
        int x = begin.fi + bias[i][0], y = begin.se + bias[i][1];
        if( x < 1 || x > n || y < 1 || y > m ) continue;
        if( ch[x][y] == 'x' ) continue;
        if( ch[x][y] == 't' ) return true;
        if( dfs({x, y}) ) return true;
    }
    return false;
}

// bfs算法
bool bfs( node begin ){
    qe.push(begin);
    while( !qe.empty() ){
        node now = qe.front(); qe.pop();
        for( int i = 0; i < 4; i ++ ){
            int x = now.fi + bias[i][0], y = now.se + bias[i][1];
            if( x < 1 || x > n || y < 1 || y > m ) continue;
            if( ch[x][y] == 'x' ) continue;
			if( ch[x][y] == 't' ) return true;
			qe.push({x, y}); ch[x][y] = 'x';
        }
    }
    return false;
}

int main() {
    int t; cin >> t;
    while( t -- ){
        cin >> n >> m;
        node begin;  // 起点专门记录一下
        for( int i = 1; i <= n; i ++ )
            for( int j = 1; j <= m; j ++ ){
                cin >> ch[i][j];
                if( ch[i][j] == 's' ) begin = {i, j};
            }
        if( dfs(begin) ) cout << "YES\n";  // 换成bfs(begin)也是可以的
        else cout << "NO\n";
        while( !qe.empty() ) qe.pop();
    }
    return 0;
}