[python刷题模板] 广度优先搜索BFS

1
2
3
度优先搜索，又称广搜，宽搜，BFS。通常用来解决最优解问题。
这将是一篇持续更新的文章，搜索太复杂了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if root is None:
return []
ans = []
q = deque()
q.append(root)
while q:
ans.append([])
width = len(q)
while width:
width -= 1
a = q.popleft()
ans[-1].append(a.val)
if a.left:
q.append(a.left)
if a.right:
q.append(a.right)
return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
q = deque()
depth = 0
q.append(root)
while q:
pre = 0
for i in range(len(q)):
a = q.popleft()
if depth&1:
# 奇数下标，必须都是偶数,且递减
if a.val&1:
return False
if i > 0 and a.val >= pre:
return False
if not depth&1:
# 偶数下标，必须都是奇数,且递增
if not a.val&1:
return False
if i > 0 and a.val <= pre:
return False
pre = a.val
if a.left:
q.append(a.left)
if a.right:
q.append(a.right)
depth += 1
return True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
# 传入顺序
def push(self, item, priority):
heapq.heappush(self._queue, (priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
def __str__(self):
return str(self._queue)
def __len__(self):
return len(self._queue)
class Status:
def __init__(self, x1=0, y1=0, x2=0, y2=0, step=0):
self.x1 = x1
# 箱子
self.y1 = y1
self.x2 = x2
# 人
self.y2 = y2
self.step = step
def __str__(self):
return str((self.x1, self.y1, self.x2, self.y2, self.step))
def __repr__(self):
return str((self.x1, self.y1, self.x2, self.y2, self.step))
class Solution:
def minPushBox(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
visited = set()
# print(visited)
floor_set = set()
q = PriorityQueue()
S, T, B = (0, 0), (0, 0), (0, 0)
for i in range(m):
for j in range(n):
if grid[i][j] == 'S':
floor_set.add((i,j))
S = (i, j)
elif grid[i][j] == 'T':
floor_set.add((i,j))
T = (i, j)
elif grid[i][j] == 'B':
floor_set.add((i,j))
B = (i, j)
elif grid[i][j] == '.':
floor_set.add((i,j))
a = Status(B[0], B[1], S[0], S[1], 0)
visited.add((a.x1,a.y1,a.x2,a.y2))
# q.push(a,a.step)
def manhattan_distance(x1, y1, x2, y2):
return abs(x1 - x2) + abs(y1 - y2)
def euclidean_distance2(x1, y1, x2, y2):
return (x1 - x2) ** 2 + (y1 - y2) ** 2
q.push(a,
(manhattan_distance(a.x1, a.y1, T[0], T[1])+a.step))
def in_bound(x,y):
return (x,y) in floor_set
def can_move(a, dir_x, dir_y):
# 箱子能不能向这个方向挪动
x1, y1 = a.x1 + dir_x, a.y1 + dir_y
# 箱子动
if not in_bound(x1, y1):
# 箱子出界
return False
if (x1,y1,a.x1,a.y1) in visited:
# 访问过
return False
x, y = a.x1 - dir_x, a.y1 - dir_y
# 判断人是否可以到达箱子后边
if not in_bound(x, y) or not can_arrive(a, x, y):
return
return True
def move(a, dir_x, dir_y):
b = Status(a.x1 + dir_x, a.y1 + dir_y, a.x1, a.y1, a.step + 1)
visited.add((b.x1,b.y1,b.x2,b.y2))
return b
def can_arrive(a, x, y):
if a.x2 == x and a.y2 == y:
return True
q1 = PriorityQueue()
visited_2 = set()
q1.push((a.x2, a.y2),euclidean_distance2(a.x2,a.y2,x,y))
visited_2.add((a.x2,a.y2))
while q1:
xb, yb = q1.pop()
for x1, y1 in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
x2, y2 = xb + x1, yb + y1
if x2 == x and y2 == y:
return True
if in_bound(x2, y2) and (x2,y2) not in visited_2 and not (x2 == a.x1 and y2 == a.y1):
q1.push((x2, y2),euclidean_distance2(x2,y2,x,y))
visited_2.add((x2,y2))
return False
while len(q):
# print(q)
a = q.pop()
if a.x1 == T[0] and a.y1 == T[1]:
return a.step
for x1, y1 in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
if can_move(a, x1, y1):
b = move(a, x1, y1)
# q.push(b,b.step)
q.push(b, (
manhattan_distance(b.x1, b.y1, T[0], T[1])+b.step
))
return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
# 传入顺序
def push(self, item, priority):
# 传入两个参数，一个是存放元素的数组，另一个是要存储的元素，这里是一个元组。
heapq.heappush(self._queue, (priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
def __str__(self):
return str(self._queue)
def __len__(self):
return len(self._queue)
class Solution:
def cutOffTree(self, forest: List[List[int]]) -> int:
m,n = len(forest),len(forest[0])
if forest[0][0] == 0:
return -1
fathers = [[(0,0)]*n for _ in range(m)]
# 并查集

trees = [(0,0,0)]
floors = set()
for i in range(m):
for j in range(n):
h = forest[i][j]
fathers[i][j] = (i,j)
if h > 1:
trees.append((h,i,j))
if h > 0:
floors.add((i,j))
trees.sort()
# print(fathers)
def find_father(x,y):
x1,y1 = fathers[x][y]
if (x1,y1) != (x,y):
fathers[x][y] = find_father(x1,y1)
# 压缩路径
return fathers[x][y]
for i in range(m):
for j in range(n):
if forest[i][j] == 0:
continue
for x,y in [(i-1,j),(i,j-1)]:
if (x,y) not in floors:
continue
x1,y1 = find_father(x,y)
fathers[x1][y1] = find_father(i,j)
for i,j in floors:
if find_father(0,0) != find_father(i,j):
# print(i,j, find_father(i,j))
return -1
def manhadun(x1,y1,x2,y2):
return abs(x1-x2)+abs(y1-y2)
def bfs(x,y,x_tar,y_tar):
if x == x_tar and y == y_tar:
return 0
visited = set()
q = PriorityQueue()
q.push((x,y,0),manhadun(x,y,x_tar,y_tar))
# q.push((x,y,0),(0,manhadun(x,y,x_tar,y_tar)))
# q.push((x,y,0),0)
visited.add((x,y))
while q:
x,y,step = q.pop()
if x == x_tar and y == y_tar:
return step
for x1,y1 in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if (x1,y1)
not in floors or (x1,y1)
in visited:
continue
# q.push((x1,y1,step+1),step+1)
# q.push((x1,y1,step+1),(step+1,manhadun(x1,y1,x_tar,y_tar)))
q.push((x1,y1,step+1),(step+1,manhadun(x1,y1,x_tar,y_tar)+step+1))
visited.add((x1,y1))
return -1
def bfs2(x,y,x_tar,y_tar):
if x == x_tar and y == y_tar:
return 0
visited = set()
q = deque()
q.append((x,y,0))
visited.add((x,y))
while q:
x,y,step = q.popleft()
if x == x_tar and y == y_tar:
return step
for x1,y1 in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
if (x1,y1)
not in floors or (x1,y1)
in visited:
continue
# q.push((x1,y1,step+1),step+1)
# q.push((x1,y1,step+1),(step+1,manhadun(x1,y1,x_tar,y_tar)))
q.append((x1,y1,step+1))
visited.add((x1,y1))
return -1
ans = 0
for i in range(1,len(trees)):
h1,x1,y1 = trees[i-1]
h2,x2,y2 = trees[i]
r = bfs(x1,y1,x2,y2)
if r == -1:
return -1
ans += r
return ans
"""
1 2 3
0 0 4
7 6 5
"""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
def minimumObstacles(self, grid: List[List[int]]) -> int:
# 最短路模板题
m,n = len(grid),len(grid[0])
graph = collections.defaultdict(dict)
for i in range(m):
for j in range(n):
for x,y in [(i+1,j),(i,j+1)]:
if x<m and y<n:
graph[(i,j)][(x,y)] = grid[x][y]
graph[(x,y)][(i,j)] = grid[i][j]
def dijkstra(graph,start):
from queue import PriorityQueue
dist =
collections.defaultdict(lambda :float("inf"))
# 初始化距离数组
dist[start] = 0
# 原点到自己是0
visited = set([start])
# 访问过原点了
q = PriorityQueue()
for v,w in graph[start].items():
# 找到所有原点的邻居，更新他们的dist
dist[v] = w
q.put((w,v))
# 权放前边，注意是put
while not q.empty():
x,u = q.get()
# 用u给别的节点做松弛，注意是get
if u in visited:
continue
visited.add(u)
for v,w in graph[u].items():
new_dist = dist[u]+w
if new_dist < dist[v]:
dist[v] = new_dist
if v not in visited:
q.put((new_dist,v))
return dist
dist = dijkstra(graph,(0,0))
return
dist[(m-1,n-1)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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<=x<m and 0<=y<n
dist = [[inf]*n for _ in range(m)]
dist[0][0] = 0
q = [(0,0,0)]
while q:
c,x,y = heapq.heappop(q)
if x == m-1 and y == n - 1:
return c
if c > dist[x][y]:continue
for dx,dy in DIRS:
a,b = x+dx,y+dy
if inside(a,b) :
d = c+grid[a][b]
if dist[a][b]>d:
dist[a][b] = d
heapq.heappush(q,(d,a,b))
return -1