题目理解

我们有一个 $R \times C$ 的迷宫，包含墙(#)、空地(.)、起点(S)和终点(C)。
可以在相邻空地间移动，花费 1 单位时间。
此外可以使用传送枪：向四个方向之一发射传送门，直到碰到墙，传送门会放在墙上。
最多同时存在两个传送门，新的会替代旧的。当两个传送门都存在时，可以从一个传送到另一个，花费 1 单位时间。
目标：从起点到终点的最短时间。

---

问题转化

将迷宫建模为图：

• 节点：每个空地位置 $(i,j)$
• 边分两种：
  1. 普通移动：相邻空地间连边，权值 = 1
  2. 传送移动：从当前位置到某个方向墙边的特定位置连边，权值 = 当前位置到墙的距离 + 1

---

关键思路

1. 传送机制抽象

一次完整的传送过程：

1. 在位置 $P$ 向某方向发射门，门落在墙 $W_1$ 上
2. 在另一位置向某方向发射门，门落在墙 $W_2$ 上
3. 从 $P$ 走到 $W_1$ 旁的空地 $A$，进入传送门，从 $W_2$ 旁的空地 $B$ 出来

代码将其简化为：从 $P$ 直接连边到 $B$，权值 = $P$ 到 $W_1$ 的步数 + 1（传送时间）

2. 墙距离预处理

用 BFS 从所有墙位置出发，计算每个位置到最近墙的曼哈顿距离：

// 初始化：墙的 wdis = -1
// BFS 扩散：wdis[邻居] = wdis[当前] + 1

这样 wdis[i][j] 表示从 $(i,j)$ 到最近墙的步数 + 1

3. 传送边构建

对每个空地的四个方向：

• 左方向：找到该行左边最近的墙边空地 $(i, wal)$ 连边 $(i,j) \to (i,wal)$，权值 = wdis[i][j]
• 同理处理右、上、下方向

---

算法步骤

1. 地图扩展

n += 2; m += 2;
memset(a, '#', sizeof(a));

周围加一圈墙，简化边界处理。

2. 计算墙距离

for 所有墙位置:
    wdis[i][j] = -1, 加入队列
while 队列非空:
    取出 (x,y), d = wdis[x][y]
    for 四个邻居 (nx,ny):
        if wdis[nx][ny] 未访问:
            wdis[nx][ny] = d + 1
            加入队列

3. 建图

// 普通移动边
for 每个空地 (i,j):
    for 四个邻居 (nx,ny):
        if (nx,ny) 是空地:
            添加边 (i,j)->(nx,ny)，权值 1

// 传送边 - 左方向
for i = 1 to n:
    wal = 最左墙位置
    for j = 1 to m:
        if a[i][j] 是空地:
            添加边 (i,j)->(i,wal)，权值 wdis[i][j]
        if a[i][j+1] 是墙:
            wal = j  // 更新墙位置

同理处理右、上、下方向。

4. 最短路计算

初始化 dis[sx][sy] = 0
队列.push((sx,sy))
while 队列非空:
    取出 (x,y), d = dis[x][y]
    for 每条边 (x,y)->(nx,ny)，权值 w:
        if dis[nx][ny] > d + w:
            dis[nx][ny] = d + w
            加入队列
输出 dis[tx][ty]

---

复杂度分析

• 预处理：$O(RC)$
• 建图：$O(RC)$
• 最短路：$O(RC \log RC)$（应使用优先队列）

---

样例验证

输入：

4 4
.#.C
.#.#
....
S...

过程：

1. 从 S 向右走 2 步到 (4,3)
2. 使用传送：花费 wdis[4,3] = 2 到达 C 附近
3. 再走 1 步到 C 总时间 = 2 + 2 = 4

---

算法标签

• 图论
• 最短路
• 建模转化
• BFS

---

总结

本题通过将传送机制抽象为特殊的图边，把复杂的三维状态（位置+传送门状态）简化为二维图最短路问题。
关键是把"发射传送门+传送"的过程建模为从当前位置直接到目标墙边空地的单条边，权值包含走到墙和传送的时间。
这样就能用标准最短路算法高效求解。