@@ -13,7 +13,7 @@ def DFS(x):
1313return
1414```
1515
16- - 先序，迭代
16+ - 先序，迭代，出栈时访问
1717
1818``` Python
1919def DFS (x ):
@@ -22,7 +22,6 @@ def DFS(x):
2222 v= dfs.pop()
2323if not visited(v):
2424 visit(v)
25-
2625for nin neighbor(v):
2726if not visited(n):
2827 dfs.append(n)
@@ -49,31 +48,31 @@ def DFS(x): # used when need to aggregate results from children
4948
5049``` Python
5150def BFS (x ):
51+ visit(x)
5252 bfs= collections.deque([x])
5353while bfs:
5454 v= bfs.popleft()
55- if not visited(v):
56- visit(v)
57- for nin neighbor(v):
58- if not visited(v):
59- bfs.append(n)
55+ for nin neighbor(v):
56+ if not visited(n):
57+ visit(n)
58+ bfs.append(n)
6059return
6160```
6261
6362- 以层为单位搜索，典型应用是找不带权的最短路径
6463
6564``` Python
6665def BFS (x ):
66+ visit(x)
6767 bfs= collections.deque([x])
6868while bfs:
6969 num_level= len (bfs)
7070for _in range (num_level)
7171 v= bfs.popleft()
72- if not visited(v):
73- visit(v)
74- for nin neighbor(v):
75- if not visited(v):
76- bfs.append(n)
72+ for nin neighbor(v):
73+ if not visited(v):
74+ visit(n)
75+ bfs.append(n)
7776return
7877```
7978
@@ -90,7 +89,10 @@ inf = 2147483647
9089
9190class Solution :
9291def wallsAndGates (self rooms : List[List[int ]]) ->None :
93-
92+ """
93+ Do not return anything, modify rooms in-place instead.
94+ """
95+
9496if not roomsor not rooms[0 ]:
9597return
9698
@@ -101,28 +103,30 @@ class Solution:
101103for iin range (M):
102104for jin range (N):
103105if rooms[i][j]== 0 :
104- rooms[i][j]= inf
105106 bfs.append((i, j))
106107
107- dist= 0
108+ dist= 1
108109while bfs:
109110 num_level= len (bfs)
110111for _in range (num_level):
111112 r, c= bfs.popleft()
112- if rooms[r][c]== inf:
113- rooms[r][c]= dist
113+
114+ if r- 1 >= 0 and rooms[r- 1 ][c]== inf:
115+ rooms[r- 1 ][c]= dist
116+ bfs.append((r- 1 , c))
114117
115- if r- 1 >= 0 and rooms[r- 1 ][c]== inf:
116- bfs.append((r- 1 , c))
118+ if r+ 1 < Mand rooms[r+ 1 ][c]== inf:
119+ rooms[r+ 1 ][c]= dist
120+ bfs.append((r+ 1 , c))
117121
118- if r+ 1 < Mand rooms[r+ 1 ][c]== inf:
119- bfs.append((r+ 1 , c))
122+ if c- 1 >= 0 and rooms[r][c- 1 ]== inf:
123+ rooms[r][c- 1 ]= dist
124+ bfs.append((r, c- 1 ))
120125
121- if c- 1 >= 0 and rooms[r][c- 1 ]== inf:
122- bfs.append((r, c- 1 ))
123-
124- if c+ 1 < Nand rooms[r][c+ 1 ]== inf:
125- bfs.append((r, c+ 1 ))
126+ if c+ 1 < Nand rooms[r][c+ 1 ]== inf:
127+ rooms[r][c+ 1 ]= dist
128+ bfs.append((r, c+ 1 ))
129+
126130 dist+= 1
127131
128132return
@@ -156,24 +160,28 @@ class Solution:
156160
157161if r- 1 >= 0 :
158162if A[r- 1 ][c]== 0 :# meet and edge
163+ A[r- 1 ][c]= - 2
159164 bfs.append((r- 1 , c))
160165elif A[r- 1 ][c]== 1 :
161166 dfs.append((r- 1 , c))
162167
163168if r+ 1 < M:
164169if A[r+ 1 ][c]== 0 :
170+ A[r+ 1 ][c]= - 2
165171 bfs.append((r+ 1 , c))
166172elif A[r+ 1 ][c]== 1 :
167173 dfs.append((r+ 1 , c))
168174
169175if c- 1 >= 0 :
170176if A[r][c- 1 ]== 0 :
177+ A[r][c- 1 ]= - 2
171178 bfs.append((r, c- 1 ))
172179elif A[r][c- 1 ]== 1 :
173180 dfs.append((r, c- 1 ))
174181
175182if c+ 1 < N:
176183if A[r][c+ 1 ]== 0 :
184+ A[r][c+ 1 ]= - 2
177185 bfs.append((r, c+ 1 ))
178186elif A[r][c+ 1 ]== 1 :
179187 dfs.append((r, c+ 1 ))
@@ -182,32 +190,34 @@ class Solution:
182190 num_level= len (bfs)
183191for _in range (num_level):
184192 r, c= bfs.popleft()
185- if A[r][c] == 0 :
186- A[r][c] = - 2
187-
188- if - 1 >= 0 :
189- if A[ r- 1 ][c] == 0 :
190- bfs.append(( r- 1 , c))
191- elif A[r - 1 ][c] == 1 :
192- return flip
193-
194- if r+ 1 < M :
195- if + 1 ][c]== 0 :
196- + 1 , c))
197- elif A[r+ 1 ][c]== 1 :
198- return flip
193+
194+ if r - 1 >= 0 :
195+ if A[r - 1 ][c] == 0 :
196+ A[ r- 1 ][c] = - 2
197+ bfs.append(( r- 1 , c))
198+ elif A[ r- 1 ][c] == 1 :
199+ return flip
200+
201+ if r + 1 < M:
202+ if A[ r+ 1 ][c] == 0 :
203+ A[r+ 1 ][c]= - 2
204+ bfs.append((r+ 1 , c))
205+ elif A[r+ 1 ][c]== 1 :
206+ return flip
199207
200- if c- 1 >= 0 :
201- if A[r][c- 1 ]== 0 :
202- bfs.append((r, c- 1 ))
203- elif A[r][c- 1 ]== 1 :
204- return flip
205-
206- if c+ 1 < N:
207- if A[r][c+ 1 ]== 0 :
208- bfs.append((r, c+ 1 ))
209- elif A[r][c+ 1 ]== 1 :
210- return flip
208+ if c- 1 >= 0 :
209+ if A[r][c- 1 ]== 0 :
210+ A[r][c- 1 ]= - 2
211+ bfs.append((r, c- 1 ))
212+ elif A[r][c- 1 ]== 1 :
213+ return flip
214+
215+ if c+ 1 < N:
216+ if A[r][c+ 1 ]== 0 :
217+ A[r][c+ 1 ]= - 2
218+ bfs.append((r, c+ 1 ))
219+ elif A[r][c+ 1 ]== 1 :
220+ return flip
211221 flip+= 1
212222```
213223