[python刷题模板] 0-1BFS

• • 一、 算法&数据结构
  • • 1. 描述
    • 2. 复杂度分析
    • 3. 常见应用
    • 4. 常用优化
  • 二、 模板代码
  • • 1. 去除障碍物的矩阵搜索
    • 2. 修改传送方向的矩阵搜索
  • 三、其他
  • 四、更多例题
  • 五、参考链接

一、 算法&数据结构

1. 描述

0-1BFS目前我只在最短路问题遇到，使用双端队列优化为复杂度O(VE)。
当边权只有0或1时，可以使用0-1BFS，否则请使用dijkstra等最短路算法。
实际上0-1BFS和dijkstra是很相似的，都是控制下个节点的访问顺序；不同之处在于，dijkstra需要给堆传入优先级来决定优先访问哪个；0-1BFS的优先级是明确的。
由于复杂度提升的不多，赛中还是建议优先使用dijkstra吧。

• 当边权只有1时，我们可以用朴素BFS来找最短路；当边权有非负数时，我们可以用dijkstra。
• 它们的特点是用队列/优先队列来保证：优先出队的一定是当前最该处理的节点。
• 考虑当边权只有0或者1的情况，假设当前从u转移到v：
  • 若w=1，则v的最短路d=dist[u]+1，应入队；推之前队列中不存在dist小于d的节点。显然v应该最后出队，则dq.append(v)。
  • 若w=0，则v的最短路d=dist[u]+0=dist[u]，应入队；我们知道u是当前最小节点，如果v的优先级=u，那么完全可以立刻处理，即优先出队（下一个出队），则dq.appendleft(v)。

2. 复杂度分析

1. O(VE)，即节点数乘边数。

3. 常见应用

1. 边权只有0或1的最短路搜索。

4. 常用优化

1. dis初始化为inf，避免使用vis标记数组。

二、 模板代码

1. 去除障碍物的矩阵搜索

例题: 2290. 到达角落需要移除障碍物的最小数目

• 目标位置存在则边权是1.否则是0

DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
class Solution:def minimumObstacles(self, grid: List[List[int]]) -> int:m,n = len(grid),len(grid[0])def inside(x,y):return 0<=xd:dist[a][b] = dif grid[a][b] == 0:q.appendleft((a,b))else:q.append((a,b))                return -1

2. 修改传送方向的矩阵搜索

链接: 1368. 使网格图至少有一条有效路径的最小代价

• 显然如果顺着原方向，代价（修改次数）=0；否则代价=1.
• 代码实现时，对dir按题意顺序，然后偏移下标来模拟方向。

DIRS = [(0,1),(0,-1),(1,0),(-1,0)]
class Solution:def minCost(self, grid: List[List[int]]) -> int:m,n = len(grid),len(grid[0])def inside(x,y):return 0<=x dist[x][y]:continuefor i,(dx,dy) in enumerate(DIRS,1):a,b = x+dx,y+dy if inside(a,b):w = int(grid[x][y] != i)d = c + wif d < dist[a][b]:dist[a][b] = d if w>0:q.append((d,a,b))else:q.appendleft((d,a,b))return -1

三、其他

1. 其实用不太到这个算法，考试时候肯定是优先用dijkstra了

四、更多例题

五、参考链接

• 链接: [python刷题模板] 最短路(Dijkstra)