走迷宫

题目描述

给定 $R \times C$ 迷宫（ $1 \le R, C \le 40$ ），. 可走、# 不可走，每步只能上下左右移到相邻 .。求左上角 $(1,1)$ 到右下角 $(R,C)$ 最少要经过的格子数（含起点终点）。第一行 $R$ 、 $C$ ，接着 $R$ 行 $C$ 字符。

样例：5 5 / ..### / #.... / #.#.# / #.#.# / #.#.. → 9。

思路

把每个 . 看作顶点、四方向连边，对无权图做 BFS：起点层号记 1，每扩展一层 +1，首次到达终点时的层号就是最少经过格子数。入队即标记使每格只展开一次，复杂度 $O(RC)$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-09-30 01:47
# update_at: 2026-09-30 01:54

import sys
from collections import deque

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上、下、左、右四个移动方向


def shortest_path(maze: list[str], rows: int, cols: int) -> int | None:
    """从左上角到右下角最少经过的空地格子数（含起点和终点）；无解返回 None。"""
    # 入队即标记：每个格子只入队一次，出队时它携带的格子数就是最早到达值
    visited = [[False] * cols for _ in range(rows)]
    visited[0][0] = True
    queue = deque([(0, 0, 1)])  # (行, 列, 已经过格子数)，起点本身算 1 格
    while queue:
        row, col, cells = queue.popleft()
        if row == rows - 1 and col == cols - 1:
            return cells  # BFS 按格子数分层，首次出队即最短
        for dr, dc in DIRS:
            nr, nc = row + dr, col + dc
            can_step = 0 <= nr < rows and 0 <= nc < cols and maze[nr][nc] == "."
            if can_step and not visited[nr][nc]:
                visited[nr][nc] = True
                queue.append((nr, nc, cells + 1))
    return None  # 题面保证能走到，无解时不产生任何输出（与参考实现一致）


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    rows = int(next(data))
    cols = int(next(data))
    maze = [next(data).decode() for _ in range(rows)]  # 每行是一个整体 token
    cells = shortest_path(maze, rows, cols)
    if cells is not None:
        print(cells)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
58
59
60
61
62
63
64/**
 * 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-10-05 07:02
 * update_at: 2026-10-05 07:02
 */
// main.cpp：网格 BFS 求从左上角到右下角的最少经过格子数（含起点终点）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 45;

int R, C;
char grid[MAXN][MAXN];           // 网格，'.' 可通行，'#' 障碍
bool vis[MAXN][MAXN];            // 入队即标记，避免重复展开

int dr[4] = {-1, 1, 0, 0};       // 上、下、左、右四个移动方向
int dc[4] = {0, 0, -1, 1};

// 从左上角 (0,0) 到右下角 (R-1,C-1) 的最少经过格子数；数据保证有解。
int bfs_min_cells() {
    queue<pair<int,int>> q;
    vis[0][0] = true;
    q.push({0, 0});
    int cells = 1;               // 起点本身算 1 格
    while (!q.empty()) {
        int sz = (int)q.size();  // 当前层格子数：BFS 按层扩展，便于统计步数
        for (int i = 0; i < sz; i++) {
            auto cur = q.front(); q.pop();
            int r = cur.first;
            int c = cur.second;
            if (r == R - 1 && c == C - 1) return cells; // 首次到达终点即最短
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (grid[nr][nc] != '.') continue;
                if (vis[nr][nc]) continue;
                vis[nr][nc] = true;
                q.push({nr, nc});
            }
        }
        cells++;                 // 处理完一层，格子数 +1
    }
    return -1;                   // 防御：题面保证有解，正常不会走到这里
}

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

    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        cin >> grid[i];
    }

    int ans = bfs_min_cells();
    cout << ans << "\n";

    return 0;
}

目录

题目描述

思路

参考代码