迷宫寻路

题意

$n \times m$ 矩形迷宫，# 是墙，. 是空地。机器猫从 $(1,1)$ 出发，只能上下左右走到空地，问能否到达 $(n,m)$ 。

数据范围： $1 \leqslant n, m \leqslant 100$ ，起点和终点都是空地。

思路

最直接的想法是 DFS 回溯找路：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 11:15
 * update_at: 2026-08-05 11:15
 */
// brute.cpp：小数据暴力解，用 DFS 回溯找一条从 (1,1) 到 (n,m) 的路径。
// 与 BFS 独立实现，用来对拍验证可达性判断。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN];

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

// 从 (x, y) 出发是否有一条路能到 (n, m)
bool dfs(int x, int y) {
    if (x == n && y == m) return true;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (mp[nx][ny] == '#' || vis[nx][ny]) continue;
        vis[nx][ny] = true;
        if (dfs(nx, ny)) return true;
        vis[nx][ny] = false;   // 回溯：撤销访问
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> (mp[i] + 1);

    vis[1][1] = true;
    cout << (dfs(1, 1) ? "Yes\n" : "No\n");

    return 0;
}

DFS 每到一个格子就尝试四个方向，失败就回溯。它能判断可达性，但回溯过程中同一个格子会被反复访问，路径会绕来绕去，最坏情况效率很差。

BFS 的关键性质：按"步数从少到多"逐层扩展，每个格子第一次被访问时就是最短步数。由于本题只问能否到达，每个格子入队一次即可，不会重复搜索。

BFS 过程（样例 $3 \times 5$ 迷宫）：

text

1
2
3
4
5
6
7
8
9初始队列: [(1,1)]
第 1 层:  (2,1)
第 2 层:  (3,1)
第 3 层:  (3,2)
第 4 层:  (3,3)
第 5 层:  (2,3)
第 6 层:  (2,4)
第 7 层:  (2,5)
第 8 层:  (3,5) → 终点，输出 Yes

终点一旦被访问就立即停止，因为到达它的层数就是最短步数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 11:15
 * update_at: 2026-08-05 11:15
 */
// BFS 判断 (1,1) 能否到达 (n,m)：逐层扩展，每个点只访问一次。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
char mp[MAXN][MAXN];       // # 墙，. 空地
bool vis[MAXN][MAXN];      // 是否已入队

int dx[4] = {-1, 0, 1, 0}; // 上右下左
int dy[4] = {0, 1, 0, -1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    // 双重循环逐字符读入迷宫
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    queue<pair<int, int>> q;
    q.push({1, 1});
    vis[1][1] = true;

    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();

        if (x == n && y == m) {   // 到达终点
            cout << "Yes\n";
            return 0;
        }

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 出界
            if (mp[nx][ny] == '#') continue;                      // 墙
            if (vis[nx][ny]) continue;                            // 已访问
            vis[nx][ny] = true;
            q.push({nx, ny});
        }
    }

    cout << "No\n";
    return 0;
}

DFS 版本

本题只判断可达性，DFS 也可以直接完成：每个格子只需要访问一次，不需要回溯撤销（回溯是枚举所有路径时才需要的）。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-05 11:50
 * update_at: 2026-08-05 11:50
 */
// DFS 判断 (1,1) 能否到达 (n,m)：只判可达性时每个格子访问一次即可，不需要回溯撤销。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
char mp[MAXN][MAXN];    // # 墙，. 空地
bool vis[MAXN][MAXN];   // 是否已访问过

int dx[4] = {-1, 0, 1, 0};   // 上右下左
int dy[4] = {0, 1, 0, -1};

// 从 (x, y) 出发能否走到终点 (n, m)
bool dfs(int x, int y) {
    if (x == n && y == m) return true;

    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 出界
        if (mp[nx][ny] == '#') continue;                      // 墙
        if (vis[nx][ny]) continue;                            // 已访问
        vis[nx][ny] = true;
        if (dfs(nx, ny)) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    // 双重循环逐字符读入迷宫
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mp[i][j];

    vis[1][1] = true;
    cout << (dfs(1, 1) ? "Yes\n" : "No\n");

    return 0;
}

注意这里的 DFS 用双重循环逐字符读入迷宫：cin >> mp[i][j] 会跳过空白字符，每行字符连续读入即可，与 cin >> (mp[i] + 1) 效果相同。

DFS 与 BFS 的区别：DFS 一条路走到黑，找到终点就返回；BFS 逐层扩散。本题两者都正确，复杂度同为 $O(n \cdot m)$ 。

复杂度

每个格子至多入队一次，每次扩展 4 个方向，时间 $O(n \cdot m)$ ；空间 $O(n \cdot m)$ 。

总结

网格可达性问题的标准解法：

BFS：找最短路径 / 判断可达，每个点访问一次；
DFS：枚举所有路径 / 需要回溯构造。

图示解析

text

1
2(1,1) → (2,1) → (3,1) → (3,2) → (3,3) → (2,3) → (2,4) → (2,5) → (3,5)
 起点                                                          终点

读图方法：这是样例的 BFS 扩展顺序（每步只走一格空地）。注意 BFS 是从起点逐层向外扩散，而不是像 DFS 那样一条路走到黑再回头。

目录

题意

思路

代码

DFS 版本

复杂度

总结

图示解析