仙岛求药

题目描述

给定 $M$ 行 $N$ 列的迷宫（ $M,N\leqslant20$ ），@ 为起点，* 为仙药，# 为怪物不可走，. 为安全格。每步可上下左右移动一格，求从 @ 到 * 经过的最少方格数；若无法到达输出 -1。输入含多组数据，以 0 0 结束。

思路

把每个可通行格看成图中的一个点，四方向相邻且均可通行的点之间连一条长度为 1 的边。边权全为 1，因此从起点开始 BFS，第一次到达终点时的层号就是最短步数；队列空仍未到达则输出 -1。

参考代码

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#!/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:45
# update_at: 2026-09-30 01:45

import sys
from collections import deque

WALKABLE = '.@*'  # 三种可走格子：空地、起点、终点


def bfs(grid: list[str], start: tuple[int, int], goal: tuple[int, int]) -> int:
    """从 start 四连通走到 goal 的最少步数（不含起点，含终点），不可达返回 -1。"""
    m, n = len(grid), len(grid[0])
    dist = {start: 0}                       # 官方计数不含起点：起点距离为 0 步
    q = deque([start])
    while q:
        x, y = q.popleft()
        if (x, y) == goal:
            return dist[(x, y)]
        for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
            in_board = 0 <= nx < m and 0 <= ny < n
            if in_board and (nx, ny) not in dist and grid[nx][ny] in WALKABLE:
                dist[(nx, ny)] = dist[(x, y)] + 1
                q.append((nx, ny))
    return -1


def solve() -> None:
    data = iter(sys.stdin.read().splitlines())   # 迷宫行必须按整行消费，保留行边界
    out: list[str] = []
    while True:
        line = next(data)                         # 每组的头一行
        m, n = map(int, line.split())             # 网格规模，0 0 表示输入结束
        if m == 0 and n == 0:
            break
        grid = [next(data) for _ in range(m)]     # 迷宫的 m 行

        # 单次扫格子，同时记下起点 @ 与终点 *
        start = goal = (-1, -1)
        for i in range(m):
            for j in range(n):
                start = (i, j) if grid[i][j] == '@' else start
                goal = (i, j) if grid[i][j] == '*' else goal

        out.append(str(bfs(grid, start, goal)))

    print('\n'.join(out))


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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/**
 * 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
 */
#include <iostream>
#include <queue>
#include <utility>
#include <string>
using namespace std;

typedef long long ll;

const ll MAXM = 25;
const ll MAXN = 25;

char grid[MAXM][MAXN]; // 迷宫网格
ll dist[MAXM][MAXN];   // 到起点的最少步数，-1 表示未访问
ll dr[4] = {-1, 1, 0, 0}; // 四方向行增量
ll dc[4] = {0, 0, -1, 1}; // 四方向列增量

// 判断格子是否在界内且可通行（非怪物）
bool walkable(ll m, ll n, ll r, ll c) {
    return r >= 1 && r <= m && c >= 1 && c <= n && grid[r][c] != '#';
}

// 从起点 (sr, sc) 走到终点 (tr, tc) 的最少步数；不可达返回 -1
ll bfs(ll m, ll n, ll sr, ll sc, ll tr, ll tc) {
    for (ll i = 1; i <= m; i++)
        for (ll j = 1; j <= n; j++)
            dist[i][j] = -1;

    queue<pair<ll, ll> > q;
    dist[sr][sc] = 0;
    q.push(make_pair(sr, sc));

    while (!q.empty()) {
        pair<ll, ll> cur = q.front();
        q.pop();
        ll r = cur.first;
        ll c = cur.second;
        if (r == tr && c == tc)
            return dist[r][c];
        for (ll k = 0; k < 4; k++) {
            ll nr = r + dr[k];
            ll nc = c + dc[k];
            if (walkable(m, n, nr, nc) && dist[nr][nc] == -1) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push(make_pair(nr, nc));
            }
        }
    }
    return -1;
}

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

    while (true) {
        ll m, n;
        cin >> m >> n;
        if (m == 0 && n == 0)
            break;
        ll sr = 0, sc = 0, tr = 0, tc = 0;
        for (ll i = 1; i <= m; i++) {
            string row;
            cin >> row;
            for (ll j = 1; j <= n; j++) {
                grid[i][j] = row[j - 1];
                if (grid[i][j] == '@') {
                    sr = i;
                    sc = j;
                } else if (grid[i][j] == '*') {
                    tr = i;
                    tc = j;
                }
            }
        }
        cout << bfs(m, n, sr, sc, tr, tc) << "\n";
    }
    return 0;
}

目录

题目描述

思路

参考代码