「JOI 2023 Final」迷宫 题解

题目大意

给定一个 $R \times C$ 的网格迷宫，每个格子是白色（.）或黑色（#）。起点 $(S_r,S_c)$ 和终点 $(G_r,G_c)$ 都是白色格子。可以使用 $N \times N$ 的印章将正方形区域内的所有格子涂白。求使得起点到终点存在路径所需的最小印章操作次数。

解题思路

核心算法：0-1 BFS（双端队列BFS）

该解法使用双端队列BFS来求解最短路径问题，其中：

• 普通移动（在白色格子上移动）：代价为0，使用队列前端
• 使用印章（在黑色格子上移动）：代价为1，使用队列后端

关键数据结构

struct node {
    long long x, y, t, h;  // 坐标(x,y), 已用印章数t, 剩余印章影响步数h
};

算法流程

1. 状态定义

每个状态包含：

• 当前位置 $(x,y)$
• 已使用的印章数量 $t$
• 印章的剩余影响步数 $h$

2. 印章机制

当使用印章时：

• 消耗1次操作（$t+1$）
• 获得 $N-1$ 步的"印章影响"（$h = N-1$）
• 在印章影响期间，可以向8个方向移动（包括对角线）

3. 状态转移

情况1：有印章影响（$h > 0$）

for (long long op = 0; op < 8; op++) {  // 8方向移动
    long long tx = u.x + dxx[op];
    long long ty = u.y + dyy[op];
    if (check(tx, ty) && !vis[fun(tx, ty)]) {
        q.push_back((node){tx, ty, u.t, u.h - 1});
    }
}

情况2：无印章影响（$h = 0$）

for (long long op = 0; op < 4; op++) {  // 4方向移动
    long long tx = u.x + dx[op];
    long long ty = u.y + dy[op];
    if (check(tx, ty) && !vis[fun(tx, ty)]) {
        if (mp[fun(tx, ty)]) {  // 黑色格子
            q.push_back((node){tx, ty, u.t + 1, n - 1});  // 使用印章
        } else {  // 白色格子
            q.push_front((node){tx, ty, u.t, 0});  // 免费移动
        }
    }
}

算法正确性分析

为什么这样设计？

1. 印章的持续性：一次印章操作不仅覆盖当前格子，还允许在接下来的 $N-1$ 步内自由移动（包括对角线）
2. 代价分层：
   • 白色格子移动：代价0（队列前端）
   • 黑色格子移动：代价1（队列后端）
3. 8方向 vs 4方向：
   • 有印章影响时，可以走对角线，模拟印章覆盖的连续区域
   • 无印章影响时，只能走上下左右

时间复杂度

• 每个格子最多访问一次：使用 vis 数组避免重复访问
• 双端队列操作：$O(1)$ 的插入删除
• 总复杂度：$O(R \times C)$

样例验证

样例1：

2×4网格，N=2
初始状态：
.###
###.

BFS过程：
- 从(1,1)开始，可以免费移动到白色格子
- 遇到黑色格子时使用印章，获得1步印章影响
- 在印章影响期内可以走对角线绕过障碍
- 最终找到路径，使用1次印章

样例4：

1×15网格，全是白色格子
- 所有移动都是免费的
- 直接输出0

代码亮点

1. 坐标压缩：使用 fun(x,y) = (x-1)*c + y 将二维坐标映射到一维
2. 双端队列优化：确保0代价操作优先处理
3. 状态设计：巧妙地将印章的持续效果编码在状态中
4. 边界检查：check(x,y) 函数确保不越界

总结

这个解法通过巧妙的状态设计和双端队列BFS，将复杂的印章覆盖问题转化为标准的最短路径问题。关键在于：

1. 印章的持续性效果：一次印章操作产生多步的影响
2. 代价分层处理：区分免费移动和付费移动
3. 方向灵活性：根据是否有印章影响调整移动方向

该算法在 $R \times C \leq 6 \times 10^6$ 的数据规模下能够高效运行，是一个优秀的解决方案。