题解 | 红魔馆的走廊清理

红魔馆的走廊清理

https://www.nowcoder.com/practice/2188d460b6de4daab94d6b0e60200187

REALHW162 红魔馆的走廊清理（Dijkstra 解法）

解题思路

求网格中从 (0,0) 到 (m-1,n-1) 的最少转向次数，只能向右或向下移动。

将每个格子拆成两个状态：(行, 列, 到达方向)。两个状态之间的转移代价为 0（同方向）或 1（转向了），用 Dijkstra 求最短路即可。

为什么状态要带方向？

转向次数取决于"上一步方向"和"这一步方向"是否相同。如果只存 dist[i][j]，就不知道上一步从哪个方向来，无法判断下一步是否算转向。

边权设计

从状态 (i, j, d) 出发：

向右走 → (i, j+1, 0)：若 d=0（本来就是向右），代价 0；若 d=1（从向下改为向右），代价 1
向下走 → (i+1, j, 1)：若 d=1（本来就是向下），代价 0；若 d=0（从向右改为向下），代价 1

简化为：代价 = (当前方向 ≠ 下一步方向) ? 1 : 0

代码实现

import heapq

m, n = map(int, input().split())
if m <= 0 or n <= 0 or m > 100 or n > 100:
    print(-1)
    exit()

grid = [list(map(int, input().split())) for _ in range(m)]

if grid[0][0] != 0 or grid[m-1][n-1] != 0:
    print(-1)
    exit()

INF = float('inf')
# dist[i][j][d]: 到达 (i,j)，最后一步方向为 d 的最少转向次数
# d=0 向右, d=1 向下
dist = [[[INF, INF] for _ in range(n)] for _ in range(m)]
dist[0][0][0] = dist[0][0][1] = 0

# 优先队列: (转向次数, 行, 列, 方向)
pq = [(0, 0, 0, 0), (0, 0, 0, 1)]

while pq:
    cost, i, j, d = heapq.heappop(pq)
    if cost > dist[i][j][d]:
        continue

    # 向右走到 (i, j+1)
    if j + 1 < n and grid[i][j + 1] == 0:
        nc = cost + (1 if d == 1 else 0)  # 方向变了就 +1
        if nc < dist[i][j + 1][0]:
            dist[i][j + 1][0] = nc
            heapq.heappush(pq, (nc, i, j + 1, 0))

    # 向下走到 (i+1, j)
    if i + 1 < m and grid[i + 1][j] == 0:
        nc = cost + (1 if d == 0 else 0)
        if nc < dist[i + 1][j][1]:
            dist[i + 1][j][1] = nc
            heapq.heappush(pq, (nc, i + 1, j, 1))

ans = min(dist[m-1][n-1])
print(ans if ans < INF else -1)

代码解析

以示例 3×3 网格为例：

0  ×  0
0  0  0
×  0  0

起点 (0,0) 两个方向代价都为 0，放入优先队列。

优先队列处理过程（按代价从小到大弹出）：

弹出 (0, 0,0,0) cost=0  → 向下到 (1,0,1) cost=1
弹出 (0, 0,0,1) cost=0  → 向右到 (1,1,0)... 不对，(0,1)是障碍物
                       → 向下到 (1,0,1) cost=0（同方向不转向）
弹出 (1,0,1) cost=0     → 更新成功，向下到 (1,0,1) cost=0
                       → 向右到 (1,1,0) cost=1（转向了）
弹出 (1,1,0) cost=1     → 向右到 (1,2,0) cost=1
                       → 向下到 (2,1,1) cost=2（转向了）
弹出 (1,2,0) cost=1     → 向下到 (2,2,1) cost=2（转向了）
弹出 (2,1,1) cost=2     → 向右到 (2,2,0) cost=3（转向了）
弹出 (2,2,1) cost=2     → 终点到达
弹出 (2,2,0) cost=3     → 更差，跳过

终点 dist[2][2] = [3, 2]，取 min = 2。

Dijkstra 的正确性保证：优先队列每次弹出当前代价最小的状态，一旦某个状态被弹出，它的代价就是最优的（不可能被后续更新）。这就是 if cost > dist[i][j][d]: continue 的作用——跳过已过时的队列条目。