520B 用普通 BFS 处理单位代价，20C 用 Dijkstra 处理一般非负边权。这一次，我们把边权限制为 0 和 1，看看为什么小根堆可以换成双端队列。

不过，1063B 最值得练习的地方还在队列之前：题目同时限制左移和右移次数，为什么每个格子只需要保存一个最短距离？只有证明两个资源之间的关系，状态压缩才有依据。

1. 官方信息与问题模型

1063B · Labyrinth 官方题目 于 2026-09-09 核对：难度 1800，标签为 graphs、shortest paths，时间限制 2 秒，内存限制 512 MB。

将题意整理成一个模型：在有障碍的矩形网格中，从给定空格出发，每步走向一个相邻空格；上下不限次数，左移至多 x 次，右移至多 y 次。求有多少个格子能由某条符合预算的路径到达，起点也算一个。

官方约束 算法含义
1 ≤ n,m ≤ 2000 最多四百万个格子，不宜为每格分配复杂容器
0 ≤ x,y ≤ 10^9 不能把预算直接作为大规模 DP 数组维度
起点行列为 1-based，且保证为空格 读入后统一减一，起点距离为 0
. 为空格，* 为障碍 只在相邻空格间生成边，无需显式邻接表

这里的“可达”是逐个格子的存在性判断，不要求用同一条路径访问所有计入答案的格子。

2. 为什么朴素搜索不够

直接记录 (行, 列, 已左移次数, 已右移次数) 是容易理解的正确模型，但状态上界会带上 (x+1)(y+1)，无法应对十亿预算。它适合小数据验证，不适合提交。

只记录“这个格子是否访问过”的普通 BFS 则换了优化目标：它先找到的是总步数最少的路径。上下走很远但不消耗左移预算的路线，可能比走得短但频繁横移的路线更有价值。第一次入队不能据此锁定最佳资源消耗。

如果已经得到正确的 0/1 权重，直接用 Dijkstra 也能求解；它的堆操作会增加对数因子。我们先推导权重，再利用只有两种边权的特殊结构。

3. 位移守恒：右移次数可以算出来

起点列为 c，到达目标列 j 的一条路径左移 L 次、右移 R 次。上下移动不改变列，每次右移加一、左移减一，因此：

1
2
R - L = j - c
R = L + j - c

对同一个目标格子，j-c 是常数。若两条路径满足 L₁ < L₂，必有 R₁ < R₂。所以在这个格子上，左移更少的路径同时也右移更少，不存在“省左移却多花右移”的权衡。

于是定义：

1
dist[i][j] = 从起点到 (i,j) 的最少左移次数

如果格子可达，其对应的最少右移次数就是 dist[i][j] + j - c。这里两者由同一条最少左移路径同时实现，并非分别求两个可能无法兼容的最优值。

这一步不能机械迁移到任意双资源问题。如果移动还会消耗燃料、钥匙或时间，而它们不能由位置和一个资源唯一确定，就可能需要保留多个互不支配的状态。

4. 把移动变成有向 0/1 边

移动 左移次数变化 边权 成功松弛后放在哪里
上 0 0 队首
下 0 0 队首
右 0 0 队首
左 1 1 队尾

右移边权为 0 只表示它不增加当前距离指标——左移次数，并不表示右移预算无限。右移限制会在最后检查。

几何上相邻的两个空格可以互相走，但左右两个方向的边权不同，分析时要把它们看作有向边。

下面是说明队列顺序的抽象图，并非题目的网格：

若把 T 第一次入队时的距离 1 当成最终答案，就漏掉了经 A 到达 T 的代价 0。正确做法是允许严格改善距离；旧的距离记录留在队列里，弹出时再跳过。

5. 双端队列为何保持最短路顺序

队列元素保存 (入队时的距离, 格子编号)，而不只保存编号。每次弹出队首，若记录距离与最新 dist 不同，说明它已过期。

设当前弹出的有效距离是 d。队列中的记录按距离非递减排列，而且只涉及当前的两个相邻层。沿 0 权边得到 d，插到队首；沿 1 权边得到 d+1，插到队尾。这样就维持了顺序，不需要堆来寻找最小值。

操作 队列示意，左侧为队首
弹出有效记录 (d,u) 后 [d 的其他记录 … d+1 的记录]
0 权边改善 v [(d,v), d 的其他记录 … d+1 的记录]
1 权边改善 w [d 的记录 … d+1 的记录, (d+1,w)]
弹出旧记录 距离不一致，直接跳过，不扩展邻居

最短距离正确性。 假设某格子 u 首次以有效记录弹出时，记录值大于真实最短距离。在一条更短路径上，取第一个尚未确定的格子 v；其前驱已确定，因而曾沿路径边向 v 松弛。非负边权保证 v 的记录不会大于那条路径到 u 的总成本，故队列中应有比 u 更小的有效记录先弹出，矛盾。

这就是 Dijkstra 的选点论证，只是这里由双端队列实现按最小距离扩展。0 权边不破坏证明；负权边才会破坏所依赖的非负性。

6. 从最短距离到预算判定的证明

令目标格子的最短距离为 d，列位移为 Δ。判定条件是：

1
d 不是无穷大，并且 d ≤ x，并且 d + Δ ≤ y

必要性： 假设存在可行路径，其左右次数为 L、R。由最短距离定义有 d≤L≤x，由位移恒等式有 d+Δ≤L+Δ=R≤y。

充分性： 取一条实现最短距离 d 的真实路径，它的右移次数必为 d+Δ。若两项均不超过预算，这条路径就是可行路径。沿路左右次数只增不减，终点累计不超预算也保证每个前缀不超预算。

右移次数不会为负，因为它来自真实路径；代码仍显式检查非负，方便读者对照含义。不可达格子必须先排除，不能拿无穷大参与位移计算。

7. 手工演算：同一列也可能必须左右绕行

使用自拟网格，起点 S 位于第 1 行第 3 列，x=0,y=1。输入时将 S 换成 .：

1
2
3
..S..
..*..
.....
目标（1-based） 一条最少左移路径 d Δ 右移 d+Δ 是否计入
(1,3) 不移动 0 0 0 是
(1,4) 右 0 1 1 是
(2,4) 右、下 0 1 1 是
(3,4) 右、下、下 0 1 1 是
(3,3) 右、下、下、左 1 0 1 否，超出左移预算
(1,5) 右、右 0 2 2 否，超出右移预算
(1,2) 左 1 -1 0 否，超出左移预算

最终答案是 4。起点正下方的障碍说明：仅按目标的列差检查预算不够，必须考虑绕路；同列也不等于左右次数都是零。

8. 完整 C++17 实现

将 (i,j) 编为 i*m+j，用连续数组存距离；邻居现场计算。搜索阶段不裁剪预算，最后统一统计，使状态含义与证明一致。

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
#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <utility>
using namespace std;

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

    int n, m, r, c;
    long long x, y;
    cin >> n >> m >> r >> c >> x >> y;
    --r;
    --c;
    vector<string> grid(n);
    for (auto &row : grid) cin >> row;

    const int INF = 1000000000;
    vector<int> dist(n * m, INF);
    deque<pair<int, int>> dq; // (distance snapshot, cell id)
    const int start = r * m + c;
    dist[start] = 0;
    dq.emplace_front(0, start);

    const int dr[4] = {-1, 1, 0, 0};
    const int dc[4] = {0, 0, 1, -1};
    while (!dq.empty()) {
        auto [d, id] = dq.front();
        dq.pop_front();
        if (d != dist[id]) continue;

        const int row = id / m;
        const int col = id % m;
        for (int k = 0; k < 4; ++k) {
            const int nr = row + dr[k];
            const int nc = col + dc[k];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
            if (grid[nr][nc] == '*') continue;
            const int next = nr * m + nc;
            const int weight = (dc[k] == -1 ? 1 : 0);
            const int candidate = d + weight;
            if (candidate >= dist[next]) continue;
            dist[next] = candidate;
            if (weight == 0) dq.emplace_front(candidate, next);
            else dq.emplace_back(candidate, next);
        }
    }

    int answer = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            const int d = dist[i * m + j];
            if (d == INF) continue;
            const long long left = d;
            const long long right = left + j - c;
            if (left <= x && right >= 0 && right <= y) ++answer;
        }
    }
    cout << answer << '\n';
    return 0;
}

9. 复杂度、整数与错误清单

每个格子首次有效弹出时距离已确定；旧记录不会重复扩展邻居。每条边至多被扫描一次，每次成功松弛产生一条入队记录，总时间 O(V+E)=O(nm)。格子出度至多 4，队列连同旧记录仍为 O(E)=O(nm) 空间；网格与距离数组同样为 O(nm)。

非负权图中的最短路可以去掉环，故最少左移次数不超过 nm-1≤3,999,999。编号、距离以及最多四百万的答案都能用 int。预算及还原右移次数用 long long，无穷大不参与加法。

易错点 后果 检查方式
把右移也算成当前指标的 1 指标变成总横移，原来的还原公式失效 明确 dist 只统计左移
写成 R=L+c-j 左右方向颠倒 起点右邻格必须得到 R=1
0 权边入队尾、1 权边入队首 不再保证按最短距离扩展 对照队列不变量
第一次入队就永久标记访问 后来的更优路线无法松弛 用严格距离改善，弹出时查旧记录
相等距离也入队 上下零代价环造成无谓重复 只接受 candidate < dist[next]
忘记起点或允许穿障碍 答案偏差 单格、包围起点、单行、单列
只检查列差 忽略必须先绕行的障碍 使用上一节自拟网格

将横向两种移动都赋权 1 也能发展出另一种正确算法，但此时距离是 H=L+R，还原式必须改成 L=(H-Δ)/2,R=(H+Δ)/2。不要把两套距离定义与公式混用。

10. 用不压缩状态的算法独立对拍

验证器从本文代码块提取原始 C++17，编译后逐个输入测试，避免“文章代码”和“测试代码”各写一套。

小网格的参考算法保留 (行,列,L,R) 全部四维状态，用普通队列枚举所有预算内状态，最终对位置去重。它不使用位移公式，也不使用双端队列，可以同时检验状态压缩和最短路实现。

验证入口：tests/verify-labyrinth-article.cjs。覆盖官方两组样例、本文绕行表、所有 2×2 障碍布局的合法起点与小预算组合、固定种子随机网格，以及 2000×2000 空网格和十亿预算。大网格使用可直接计数的独立答案，检查规模与边界；随机对拍不能替代上面的正确性证明。

完成后可以返回 算法练习路径，对比三种队列：单位边权用 FIFO，0/1 边权用 deque，一般非负边权用小根堆。真正共通的目标，是让最小的待处理距离先得到扩展。