「一本通 3.2 例 2」拯救大兵瑞恩

GitHub跳转原题关系图返回列表

把状态扩成 (格子, 钥匙位掩码)，在无权状态图上 BFS 求从 (1,1) 到 (n,m) 的最短路。

OJ: roj

题目 ID: 1495

难度:提高

标签:广度优先搜索状态压缩位运算网格一本通

创建: 2026-09-30 14:42

更新: 2026-10-07 12:15

前置题目

luogu P1126[CERC1996] 机器人搬重物B 直接复用 A 教的状态设计：只记坐标会漏解，必须把影响未来的附加信息（这里是钥匙掩码）并入状态维度，再做无权网格 BFS 首次到达即最短。roj 3003最短Hamilton路径B 的钥匙态状态设计直接复用 A 教的关键观察：把影响未来的离散集合（A 是已走点集、B 是持有钥匙集）压成整数的二进制位并作为状态的一个维度（B 代码里就是 mask 位与 key_mask 或合并后进 dist[r][c][mask]），A 是纯状压 DP 模板，B 在此之上把该位掩码状态放到网格 BFS 状态图里，再叠加门的钥匙位判定与首次到达即最短路。

形式化题目

有一个 $n$ 行 $m$ 列的网格，格子用 $(r,c)$ 表示，相邻格子之间距离为 $1$ 。

相邻两格之间可能有一扇第 $g$ 类门（ $1 \leqslant g \leqslant p$ ），可能有一堵墙，也可能什么都没有。没有出现在输入里的相邻格子之间既无门也无墙。
若干格子上放有钥匙，一把钥匙只对应一个门的类别 $q$ ；持有第 $q$ 类钥匙即可打开所有第 $q$ 类门，开门不消耗钥匙。
拿钥匙与开门都不额外耗时。

求从 $(1,1)$ 出发走到 $(n,m)$ 的最少步数；若无法到达则输出 $-1$ 。

样例的迷宫可以画成下面这张图（. 表示空地、数字表示该格钥匙类别、█ 表示墙、D1/D2 表示门、— 表示自由通行）：

text

1
2
3
4
5
6
71,1   —   1,2  D2  1,3   —   1,4
  —         █         —         —
2,1   █   2,2   —   2,3   —   2,4
  █         —         █        D1
3,1   —   3,2   █   3,3   —   3,4
  —         —         █         —
4,1   —   4,2   —   4,3   █   4,4

注意 (1,2)–(2,2)、(2,1)–(2,2)、(2,1)–(3,1)、(2,3)–(3,3)、 (3,2)–(3,3)、(3,3)–(4,3)、(4,3)–(4,4) 这几对格子之间是墙，而 (1,2)–(1,3) 是 2 类门、(2,4)–(3,4) 是 1 类门。

正解

思路

先看只按格子做 BFS 错在哪里。 假设访问标记只记 $(r,c)$ ：第一次到 $(r,c)$ 时手里可能只有钥匙 $\{2\}$ ，于是 $(r,c)$ 被标记为"已访问"；之后带着钥匙 $\{1,2\}$ 再次走到 $(r,c)$ 时就被剪掉，而这条路径本来能打开 1 类门继续前进。可见"手里有哪些钥匙"是会影响未来的信息，只记位置会漏解。

补全状态。 影响未来的附加信息只有钥匙集合，而门总共不超过 $p \leqslant 10$ 类，正好用一个 $p$ 位掩码存下：mask 的第 $q-1$ 位为 $1$ 表示持有第 $q$ 类钥匙。把状态定义为三元组 $(r,c,\text{mask})$ ，含义是"站在 $(r,c)$ ，手里有 mask 这些钥匙"。

转移。 从状态 $(r,c,\text{mask})$ 走向相邻格 $(r_2,c_2)$ 时，先看两格之间的编码 $g$ ：

输入中的 $g$	含义	能否通过
未登记	既无门也无墙	能
$g = 0$	一堵墙	永远不能
$g \geqslant 1$	第 $g$ 类门	需要 `mask` 的第 $g-1$ 位为 $1$

落脚之后， $(r_2,c_2)$ 上的钥匙顺手就拿走，所以新状态是 $(r_2,c_2,\text{mask} \mid \text{keys}[r_2][c_2])$ 。按题面"拿钥匙不耗时"，这一步不增加距离。

为什么可以用 BFS。 每条边的代价都是 $1$ ，所以 BFS 的出队顺序就是距离从小到大的顺序。更关键的是 mask 只增不减：同一个状态 $(r,c,\text{mask})$ 的后续走法完全由状态本身决定，不存在"多绕几步得到同一状态却更有用"的情况。于是每个状态只需入队一次，第一次访问它的距离就是最短距离，第一次弹出 $(n,m)$ 状态时即可直接输出答案。

下面这张图是样例中一条路径的状态转移，节点写成 (r,c,钥匙位)：

graph LR
    A["(1,1, 00)"] -->|"下"| B["(2,1, 10)"]
    B -->|"上"| C["(1,1, 10)"]
    C -->|"右"| D["(1,2, 10)"]
    D -->|"右穿门2"| E["(1,3, 10)"]
    E -->|"下"| F["(2,3, 10)"]
    F -->|"左"| G["(2,2, 10)"]
    G -->|"下"| H["(3,2, 10)"]
    H -->|"下"| I["(4,2, 11)"]
    I -->|"上"| J["(3,2, 11)"]
    J -->|"上"| K["(2,2, 11)"]
    K -->|"右"| L["(2,3, 11)"]
    L -->|"右穿门1"| M["(2,4, 11)"]
    M -->|"下"| N["(3,4, 11)"]
    N -->|"下"| O["(4,4, 11)"]

读者应重点观察两件事：一是拿到第 1 类钥匙后掩码从 10 变成 11，才得以通过 (2,3)–(2,4) 之间的门 1；二是中途出现 (2,2,10) 与 (2,2,11)、(3,2,10) 与 (3,2,11) 这样"同一格子、不同掩码"的两个状态，它们在同一层网格上不可合并，这正是状态必须扩展的原因。整条路径共 $14$ 步，与样例输出一致。

代码

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#!/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 14:39
# update_at: 2026-09-30 14:44

import sys
from collections import deque

FREE = -1  # 格间编码：-1 = 未出现在输入里，即无门无墙，直接可走
WALL = 0   # 格间编码：0 = 不可逾越的墙


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m, p = next(data), next(data), next(data)

    # gate[(r, c, r2, c2)]：相邻两格之间的门类型。-1 自由通行，0 是墙，>=1 是第 g 类门。
    gate: dict[tuple[int, int, int, int], int] = {}
    k = next(data)
    for _ in range(k):
        r1, c1, r2, c2, g = next(data), next(data), next(data), next(data), next(data)
        gate[(r1, c1, r2, c2)] = gate[(r2, c2, r1, c1)] = g  # 门是双向的，两个方向都登记

    # keys[r][c]：该格钥匙集合的位掩码；一把都没有时为 0。
    keys = [[0] * (m + 1) for _ in range(n + 1)]
    s = next(data)
    for _ in range(s):
        x, y, q = next(data), next(data), next(data)
        keys[x][y] |= 1 << (q - 1)  # 同类钥匙重复无意义，用或运算合并

    # 状态 (r, c, mask) = 站在 (r, c) 且已持有钥匙集合 mask。
    # 每格钥匙一到达就自动收进 mask，mask 只增不减，所以状态图无环，BFS 分层即可。
    start = keys[1][1]
    dist = {(1, 1, start): 0}
    queue = deque([(1, 1, start)])

    while queue:
        r, c, mask = queue.popleft()
        if (r, c) == (n, m):  # 队列按距离递增出队，首次弹出终点即最短时间
            print(dist[(r, c, mask)])
            return
        step = dist[(r, c, mask)] + 1
        for r2, c2 in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if not (1 <= r2 <= n and 1 <= c2 <= m):
                continue
            g = gate.get((r, c, r2, c2), FREE)
            if g == WALL:
                continue                                    # 墙永远不可逾越
            opened = g == FREE or mask >> (g - 1) & 1       # 门要有对应钥匙才能穿
            nxt = (r2, c2, mask | keys[r2][c2])             # 落脚即拾取该格钥匙
            if opened and nxt not in dist:
                dist[nxt] = step
                queue.append(nxt)

    print(-1)  # 状态空间全部搜完仍未到达 (n, m)


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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147/**
 * 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 04:25
 * update_at: 2026-10-05 04:25
 */
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

typedef long long ll;

const int MAXN = 12;         // n, m <= 10，留一点余量
const int MAXP = 10;         // 门与钥匙的类别数 p <= 10
const int MAXMASK = 1 << MAXP;
const int FREE = -1;         // 相邻两格未出现在输入里：既无门也无墙，自由通行
const int WALL = 0;          // g = 0 表示一堵不可逾越的墙

int n, m, p;

// 方向编号：0 上、1 下、2 左、3 右
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

// gate[r][c][d]：从 (r,c) 朝方向 d 的相邻格间编码。
// FREE = 自由通行，WALL = 墙，g >= 1 = 第 g 类门（双向登记）。
int gate[MAXN][MAXN][4];

// key_mask[r][c]：该格钥匙集合的位掩码，第 q-1 位为 1 表示放着第 q 类钥匙。
int key_mask[MAXN][MAXN];

// dist[r][c][mask]：到达状态 (r,c,mask) 的最少步数，-1 表示该状态还没访问过。
// 距离最大不超过状态总数 10*10*1024，用 int 足够并省内存。
int dist[MAXN][MAXN][MAXMASK];

// 状态 (r,c,mask)：站在格子 (r,c)，手里持有钥匙集合 mask 的那些钥匙。
struct State {
    int r;
    int c;
    int mask;
};

// 在状态图上 BFS：每条边代价都是 1，首次弹出终点即为最短时间；搜完仍未到达返回 -1。
ll bfs() {
    queue<State> q; // BFS 队列，出队顺序按步数从小到大

    int start_mask = key_mask[1][1]; // 起点 (1,1) 的钥匙顺手拿走
    dist[1][1][start_mask] = 0;
    State first;
    first.r = 1;
    first.c = 1;
    first.mask = start_mask;
    q.push(first);

    while (!q.empty()) {
        State cur = q.front();
        q.pop();

        if (cur.r == n && cur.c == m) {
            return dist[cur.r][cur.c][cur.mask];
        }

        int nxt_step = dist[cur.r][cur.c][cur.mask] + 1;
        for (int d = 0; d < 4; d++) {
            int r2 = cur.r + dr[d];
            int c2 = cur.c + dc[d];
            if (r2 < 1 || r2 > n || c2 < 1 || c2 > m) {
                continue;
            }

            int g = gate[cur.r][cur.c][d];
            if (g == WALL) {
                continue; // 墙永远不能穿过
            }
            if (g >= 1 && ((cur.mask >> (g - 1)) & 1) == 0) {
                continue; // 是门，但手里没有这一类钥匙，开门不消耗钥匙
            }

            int new_mask = cur.mask | key_mask[r2][c2]; // 落脚后拾取该格钥匙，拿钥匙不耗时
            if (dist[r2][c2][new_mask] != -1) {
                continue; // 状态只入队一次，同一个状态决不会被重复处理
            }
            dist[r2][c2][new_mask] = nxt_step;

            State next_state;
            next_state.r = r2;
            next_state.c = c2;
            next_state.mask = new_mask;
            q.push(next_state);
        }
    }

    return -1; // 全部状态搜完仍到不了 (n,m)
}

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

    memset(gate, FREE, sizeof(gate)); // 未登记的相邻格统一置成 -1，即自由通行
    memset(dist, -1, sizeof(dist));

    cin >> n >> m >> p;

    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int x1, y1, x2, y2, g;
        cin >> x1 >> y1 >> x2 >> y2 >> g;

        // 题目保证两格相邻，先由相对位置定出双向的方向编号
        int d1, d2;
        if (x1 == x2) {
            if (y2 == y1 + 1) {
                d1 = 3; // (x1,y1) -> 右
                d2 = 2; // (x2,y2) -> 左
            } else {
                d1 = 2;
                d2 = 3;
            }
        } else {
            if (x2 == x1 + 1) {
                d1 = 1; // (x1,y1) -> 下
                d2 = 0; // (x2,y2) -> 上
            } else {
                d1 = 0;
                d2 = 1;
            }
        }
        gate[x1][y1][d1] = g;
        gate[x2][y2][d2] = g; // 门和墙都是双向的，两个方向都要登记
    }

    int s;
    cin >> s;
    for (int i = 1; i <= s; i++) {
        int x, y, q;
        cin >> x >> y >> q;
        key_mask[x][y] |= 1 << (q - 1); // 同类钥匙重复出现没有额外作用，用或运算合并
    }

    cout << bfs() << "\n";

    return 0;
}

复杂度

状态数为 $n \cdot m \cdot 2^p$ ，每个状态枚举 $4$ 个方向，故时间复杂度为 $O(nm2^p)$ ，空间复杂度同为 $O(nm2^p)$ 。取 $n=m=p=10$ 时约 $4.1 \times 10^5$ 次转移。

总结

当"当前手里的东西"会决定未来能走哪些边时，必须把它并入状态，否则任何访问剪枝都会漏解。
类别数 $p \leqslant 10$ 是使用位掩码的信号： $2^p$ 的状态上限完全可枚举。
钥匙只增不减 ⇒ 状态图无环 ⇒ 无权图上 BFS 首次到达即最短，不需要 Dijkstra 或松弛操作。
实现上要注意题面的编码约定： $g = 0$ 是墙， $g \geqslant 1$ 才是门，输入里没出现的相邻格才是自由通行，三者不能混为一谈。

【题目描述】

1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 $n$ 行，东西方向被划分为 $m$ 列，于是整个迷宫被划分为 $n×m$ 个单元。每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。南北或东西方向相邻的 $2$ 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成 $p$ 类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即 ( $n,m$ ) 单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入 ( $1,1$ ) 单元。另外，麦克从一个单元移动到另一个相邻单元的时间为 $1$ ，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

【输入】

第一行有三个整数,分别表示 $n,m,p$ 的值。

第二行是一个整数 $k$ ，表示迷宫中门和墙的总数。

第 $i+2$ 行 ( $1≤i≤k$ )，有 $5$ 个整数，依次为 $x\_{i1},y\_{i1},x\_{i2},y\_{i2},g\_i$ :当 $g\_i≥1$ 时，表示 ( $x\_{i1},y\_{i1}$ )单元与 ( $x\_{i2},y\_{i2}$ ) 单元之间有一扇第 $g\_i$ 类的门，当 $g\_i = 0$ 时，表示 ( $x\_{i1},y\_{i1}$ ) 单元与 ( $x\_{i2},y\_{i2}$ ) 单元之间有一堵不可逾越的墙。

第 $k+3$ 行是一个整数 $s$ ，表示迷宫中存放的钥匙总数。

第 $k+3+j$ 行 ( $1≤j≤s$ ) ，有 $3$ 个整数，依次为 $x\_{i1},y\_{i1},q\_i$ ，表示第 $j$ 把钥匙存放在 ( $x\_{i1},y\_{i1}$ ) 单元里，并且第 $j$ 把钥匙是用来开启第 $q\_i$ 类门。

输入数据中同一行各相邻整数之间用一个空格分隔。

【输出】

输出麦克营救到大兵瑞恩的最短时间。如果问题无解，则输出 −1。

【输入样例】

text

【输出样例】

text

【提示】

$|x\_{i1}-x\_{i2}|+|y\_{i1}-y\_{i2}|=1,0≤g\_i≤p$

$1≤q\_i≤p$

$n,m,p≤10,k < 150$

【来源】

一本通在线评测

「一本通 3.2 例 2」拯救大兵瑞恩

目录

形式化题目

正解

思路

代码

复杂度

总结