4.2 BFS
约 2127 字大约 7 分钟
2025-01-01
提示
deque 是 Python 标准库 collections 模块中的一个类，它代表了双端队列（Double-Ended Queue）。 deque 允许从队列的两端进行高效的插入和删除操作，因此它在许多需要频繁操作两端元素的场景中比 list 更加高效。
主要特点： 双端队列：可以在队列的两端进行插入和删除操作，支持高效的 append 、 appendleft 、 pop 、 popleft 等方法。
时间复杂度：
append(x) 和 appendleft(x) ：在队列两端插入元素，时间复杂度为 O(1)。
pop() 和 popleft() ：从队列两端删除元素，时间复杂度为 O(1)。
访问队列中间的元素时，时间复杂度为 O(n)。
如果是本地编辑器编写代码，记得导入：
from collections import deque思路：开辟一个双端队列
q = deque()，先把起点加进去，然后开始while q循环，把这一轮q内的节点加进去，遍历节点的上下左右，如果遇到边界就return，遇到空地就加入q，并把当前空地改为墙。class Solution: def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int: m, n = len(maze), len(maze[0]) q = deque() q.append(entrance) # 加入起点 maze[entrance[0]][entrance[1]] = "+" # 起点视为墙 step = 0 while q: step += 1 for _ in range(len(q)): i, j = q.popleft() for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < m and 0 <= y < n and maze[x][y] == ".": if x in (0, m - 1) or y in (0, n - 1): return step q.append([x, y]) maze[x][y] = "+" return -1时间复杂度：O(mn)，其中 m 和 n 分别为 maze 的行数和列数。
空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。
提示
八方向的可以使用语句：
for x in range(i - 1, i + 2): for y in range(j - 1, j + 2):class Solution: def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int: if grid[0][0] == 1: return -1 n = len(grid) if n == 1: return 1 q = deque() q.append((0, 0)) step = 1 while q: step += 1 for _ in range(len(q)): i, j = q.popleft() temp = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)] for r, c in temp: x = i + r y = j + c if 0 <= x < n and 0 <= y < n and grid[x][y] == 0: if (x, y) == (n - 1, n - 1): return step q.append((x, y)) grid[x][y] = 1 return -1时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。
曼哈顿距离就是只能横着和竖着走；这题是多源 bfs ，先把所有陆地加入队列，每一轮循环，所有陆地都往上下左右走一步，合法的路加入队列，最终走到最后的就是最远的距离
class Solution: def maxDistance(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) q = deque() for i in range(m): for j in range(n): if grid[i][j]: q.append((i, j)) step = -1 if len(q) == m * n: return -1 while q: step += 1 for _ in range(len(q)): i, j = q.popleft() for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < m and 0 <= y < n and grid[x][y] == 0: q.append((x, y)) grid[x][y] = 1 return step时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。
也是多源 bfs ，注意将 0 视为源
class Solution: def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: m, n =len(mat), len(mat[0]) res = [[0] * n for _ in range(m)] from collections import deque q = deque() for i in range(m): for j in range(n): if mat[i][j] == 0: q.append((i, j)) step = 0 while q: step += 1 for _ in range(len(q)): i, j = q.popleft() for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < m and 0 <= y < n and mat[x][y] == 1: res[x][y] = step q.append((x, y)) mat[x][y] = 6 return res时间复杂度：O(mn)，其中 m 和 n 分别为 mat 的行数和列数。
空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。
也是多源 bfs ，将烂橘子视为源，注意要剩余新鲜橘子才进循环
class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) q = deque() fresh = 0 for i in range(m): for j in range(n): if grid[i][j] == 2: q.append((i, j)) elif grid[i][j] == 1: fresh += 1 step = 0 while q and fresh: step += 1 for _ in range(len(q)): i, j = q.popleft() for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < m and 0 <= y < n and grid[x][y] == 1: q.append((x, y)) fresh -= 1 grid[x][y] = 2 return -1 if fresh else step时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。
也是多源 bfs ，将海洋视为源，从队列中取出节点，每轮向上下左右走，合法的赋予高度，直到遍历完整个矩阵
class Solution: def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]: m, n = len(isWater), len(isWater[0]) height = [[0] * n for _ in range(m)] visited = isWater q = deque() for i in range(m): for j in range(n): if isWater[i][j]: q.append((i, j)) step = 0 while q: step += 1 for _ in range(len(q)): i, j = q.popleft() for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < m and 0 <= y < n and not visited[x][y]: height[x][y] = step q.append((x, y)) visited[x][y] = 1 return height时间复杂度：O(mn)，其中 m 和 n 分别为 isWater 的行数和列数。
空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。
求两岛之间的最短路径，把其中一个岛所在的点视为源（可以通过 dfs 做到），转化成求多源 bfs 的最短路径，只要有源走到了另一个岛即可结束，此时就是最短路径
class Solution: def shortestBridge(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1: return grid[i][j] = 2 q.append((i, j)) dfs(i - 1, j) dfs(i + 1, j) dfs(i, j - 1) dfs(i, j + 1) i, j = next((i, j) for i in range(m) for j in range(n) if grid[i][j]) # 通过迭代器找到第一个岛的一个点 q = deque() dfs(i, j) # 从这点 dfs 这个岛，并在遍历过程中把岛中的点加入 q step = -1 while q: step += 1 for _ in range(len(q)): i, j = q.popleft() for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < m and 0 <= y < n: if grid[x][y] == 1: # 走到另一个岛了 return step elif grid[x][y] == 0: # 走到海洋了 q.append((x, y)) grid[x][y] = 2 # 标记来过了时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。
这题很有意思，因为距离是最优先，故本题可以视为单源 bfs，向外走的时候把空地（
grid[i][j]为1）和物品坐标（grid[i][j]大于1）加入列表q，排序q（按照价值，行坐标，列坐标三个优先级的顺序），把合法价格（low <= grid[i][j] <= high）的坐标加入到结果res中，如果len(res)大于等于k了，说明物品足够了，返回前k个坐标，即res[:k]，如果不够继续遍历q，直到足够k个class Solution: def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]: m, n = len(grid), len(grid[0]) q = [(start[0], start[1])] res = [] visited = {(start[0], start[1])} low, high = pricing while q: # p 是一个坐标，包含横坐标和纵坐标 q.sort(key=lambda p: (grid[p[0]][p[1]], p)) res.extend(p for p in q if low <= grid[p[0]][p[1]] <= high) if len(res) >= k: return res[:k] temp = q q = [] for i, j in temp: for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in visited: q.append([x, y]) visited.add((x, y)) return res时间复杂度：O(mn)，其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度：O(mn)。即为广度优先搜索中队列需要使用的空间。