Leetcode - Dijkstra相关 | 湛蓝与蔚蓝

type

status

date

slug

summary

category

icon

password

3341. Find Minimum Time to Reach Last Room I

‣

1631. Path With Minimum Effort

‣

2577. Minimum Time to Visit a Cell In a Grid

这个稍微难一点但如果想明白每一步强迫走的实现方法就简单很多

‣

class Solution:

3286. Find a Safe Walk Through a Grid

‣

跟前几个一模一样比较简单就不放了

1293. Shortest Path in a Grid with Obstacles Elimination

‣

使用deque 根据当前行动接近目标选择添加前面还是后面添加前面有可能遇到obs 也有可能没有但是这一策略使算法永远向着最短路径前进如果条件不满足(obs数量超过) 再去考虑要走更远但是没有遇到obs的路径

注意while里的第一个if 现在total_obs(这里是用k-经过的obs 也就是还剩的容错数)必须要大于此前记录的如果小于等于那么之前没有找到的结果现在更不可能找到(因为现在不光步数比之前记录时的长 obs容错也没有优势整体肯定是更差的路径)

而 0 <= obs - grid[new_x][new_y] 则不需要考虑太多只要不超过容错随便添加