REALHW162 红魔馆的走廊清理

解题思路

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

关键观察：转向只与移动方向的变化有关。用 dp_r[i][j] 和 dp_d[i][j] 分别表示到达 (i,j) 时最后一步向右/向下的最少转向次数。

状态转移：

• 从左侧 (i,j-1) 向右走到 (i,j)：dp_r[i][j] = min(dp_r[i][j-1], dp_d[i][j-1] + 1)上一步也是向右 → 不转向上一步向下 → 转向 +1
• 从上方 (i-1,j) 向下走到 (i,j)：dp_d[i][j] = min(dp_d[i-1][j], dp_r[i-1][j] + 1)上一步也是向下 → 不转向上一步向右 → 转向 +1

起点两方向都初始化为 0（第一步不算转向），答案取 min(dp_r[end], dp_d[end])。

代码实现

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')
dp_r = [[INF] * n for _ in range(m)]
dp_d = [[INF] * n for _ in range(m)]
dp_r[0][0] = dp_d[0][0] = 0

for i in range(m):
    for j in range(n):
        if grid[i][j] != 0:
            continue
        if j > 0:
            dp_r[i][j] = min(dp_r[i][j-1], dp_d[i][j-1] + 1)
        if i > 0:
            dp_d[i][j] = min(dp_d[i-1][j], dp_r[i-1][j] + 1)

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

代码解析

以示例 3×3 网格为例（障碍物用 × 标记）：

0  ×  0
0  0  0
×  0  0

DP 值 (dp_r, dp_d) 演变过程：

(0, 0)    ×        (∞, ∞)
(∞, 0)   (1, ∞)   (1, ∞)
×        (∞, 2)   (3, 2)

终点 (2,2) 的值为 (3, 2)，取 min = 2。

对应最优路径：(0,0)→(1,0)→(1,1)→(1,2)→(2,2)，方向序列：下→右→右→下，转向 2 次。

边界处理：维度不合法输出 -1；起点或终点为障碍物输出 -1；不可达（结果为 INF）输出 -1。

复杂度分析

• 时间复杂度：O(m × n)
• 空间复杂度：O(m × n)