走出迷宫

题目描述

给定一个 $n \times m$ 的迷宫（ $1 \leqslant n,m \leqslant 100$ ），求起点到出口的最少步数；走不到则不输出任何内容。每格是 .（空地）、#（墙）、S（起点）、T（出口）之一，每步沿上、下、左、右走到相邻可通行格。

输入：第一行两个整数 $n$ 和 $m$ ；接下来 $n$ 行，每行一个长为 $m$ 的字符串表示迷宫。

输出：输出最少需要走的步数。

样例：输入 3 3、S#T、.#.、...，输出 6。

思路

每步代价相同，把可通行格看成顶点、四方向相邻看成边，答案就是 S 到 T 的最短路；边权全为 1，BFS 逐层扩展，第一次碰到 T 时的层号就是答案。每个格子入队时就标记 vis，保证只入队一次，复杂度 $O(nm)$ 。

参考代码

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#!/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 02:01
# update_at: 2026-09-30 02:04

import sys

WALL = ord('#')  # 网格按字节读入，'#' 的字节值 35 就是"不可通行"的判据

# 四个方向的 (行增量, 列增量)：上、下、左、右
DIRS: tuple[tuple[int, int], ...] = ((-1, 0), (1, 0), (0, -1), (0, 1))


def find(grid: list[bytes], key: int) -> tuple[int, int]:
    """定位标记字符 key（'S' 或 'T'）所在的 (行, 列)；题面保证它出现且只出现一次。"""
    return next(
        (r, c)
        for r, row in enumerate(grid)
        for c, ch in enumerate(row)
        if ch == key
    )


def shortest_steps(
    grid: list[bytes], n: int, m: int, start: tuple[int, int], goal: tuple[int, int]
) -> int | None:
    """四方向 BFS 返回 start→goal 的最少步数（不含起点）；不可达返回 None。

    边权全为 1，所以按层扩展：frontier 是恰好 steps 步能站到的全部格子，
    命中 goal 的那层号就是答案。格子用一维编号 r*m+c 标记，入队即标记。
    """
    seen = bytearray(n * m)
    seen[start[0] * m + start[1]] = 1
    frontier = [start]
    steps = 0
    while frontier:
        nxt: list[tuple[int, int]] = []  # 再多走一步能站到的格子
        for r, c in frontier:
            if (r, c) == goal:
                return steps
            for dr, dc in DIRS:
                nr, nc = r + dr, c + dc
                in_board = 0 <= nr < n and 0 <= nc < m  # 先判界，避免负下标悄悄读到别的行
                can_step = in_board and grid[nr][nc] != WALL and not seen[nr * m + nc]
                if can_step:
                    seen[nr * m + nc] = 1  # 入队即标记，同一个格子只展开一次
                    nxt.append((nr, nc))
        frontier, steps = nxt, steps + 1
    return None


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    m = int(next(data))
    grid: list[bytes] = [next(data) for _ in range(n)]  # 每行是一个整体 token，不按字符拆分

    steps = shortest_steps(grid, n, m, find(grid, ord('S')), find(grid, ord('T')))
    if steps is not None:  # 不连通时官方数据为空输出，这里同样不打印任何内容
        print(steps)


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
65
66
67
68
69
70/**
 * 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:12
 * update_at: 2026-10-05 07:12
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

typedef long long ll;

int n, m;
char grid[MAXN][MAXN]; // grid[r][c]：迷宫第 r 行第 c 列的字符
bool vis[MAXN][MAXN];  // vis[r][c]：该格是否已经入队，入队即标记防止重复展开
int dist[MAXN][MAXN];  // dist[r][c]：从 S 到该格的最少步数（层号）

int dr[4] = {-1, 1, 0, 0}; // 四个方向的行增量：上、下、左、右
int dc[4] = {0, 0, -1, 1};

// 从 (sr,sc) 到 (tr,tc) 的 BFS 最短路；走不到时返回 -1。
int bfs(int sr, int sc, int tr, int tc) {
    queue<pair<int, int> > q;
    vis[sr][sc] = 1;
    dist[sr][sc] = 0;
    q.push(make_pair(sr, sc));
    while (!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        if (r == tr && c == tc) return dist[r][c]; // 第一次弹出 T 时层号就是答案
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            // 合法落点：在网格内、不是墙、没有入队过
            if (nr < 1 || nr > n || nc < 1 || nc > m) continue;
            if (grid[nr][nc] == '#' || vis[nr][nc]) continue;
            vis[nr][nc] = 1;
            dist[nr][nc] = dist[r][c] + 1;
            q.push(make_pair(nr, nc));
        }
    }
    return -1; // S 所在连通分量搜完仍未到 T，无解
}

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

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

    // 扫描网格定位唯一的起点 S 和出口 T
    int sr = 0, sc = 0, tr = 0, tc = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == 'S') { sr = i; sc = j; }
            if (grid[i][j] == 'T') { tr = i; tc = j; }
        }
    }

    int ans = bfs(sr, sc, tr, tc);
    if (ans != -1) cout << ans << endl; // 无解时不输出任何内容

    return 0;
}

目录

题目描述

思路

参考代码