🗒️1824. 最少侧跳次数
2025-3-17
| 2025-3-17
0  |  阅读时长 0 分钟
type
status
date
slug
summary
tags
category
icon
password
创建时间
Mar 17, 2025 12:54 AM
给你一个长度为 n 的 3 跑道道路 ,它总共包含 n + 1 个  ,编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ,它想要跳到点 n 处。然而道路上可能有一些障碍。
给你一个长度为 n + 1 的数组 obstacles ,其中 obstacles[i] (取值范围从 0 到 3)表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ,那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。
  • 比方说,如果 obstacles[2] == 1 ,那么说明在点 2 处跑道 1 有障碍。
这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍,这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道(这两条跑道可以不相邻),但前提是跳过去的跑道该点处没有障碍。
  • 比方说,这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
这只青蛙从点 0 处跑道 2 出发,并想到达点 n 处的 任一跑道 ,请你返回 最少侧跳次数 。
注意:点 0 处和点 n 处的任一跑道都不会有障碍。

BFS

收获

这题按照 BFS 是真没思路,而且照着灵神的写法还写错了。最后,发现是初始值的原因。因为,我将 vector<vector<int>> dis = vector(3, vector(n, 0)); 的初始值设置为了 0,已经是最小了,导致后面无法判断了。 调了半天的 Bug,才发现问题,真是无语。
要仔细,不过吃一堑长一智,我是抱着学习的态度的。

📎 参考

  • 【题单】网格图(DFS/BFS/综合应用)
  • 决策树1210. 穿过迷宫的最少移动次数
    Loading...