- BFS
找到grid2中的每一座岛屿[暴力搜索整个grid矩阵]，对每座岛屿BFS，过程中check岛屿格子是否在grid1中为岛屿。
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
row, col = len(grid2), len(grid2[0])
def BFS(x:int, y:int) -> int:
grid2[x][y] = 0
q = deque()
q.append((x, y))
check = (grid1[x][y] == 1)
while(q):
x, y = q.popleft()
for nx ,ny in [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]:
if 0<=nx
- DFS
DFS第一种：找到grid2中的每一座岛屿[暴力搜索整个grid矩阵]，对每座岛屿DFS，过程中check岛屿格子是否在grid1中为岛屿。【这里用self.check作为全局变量，DFS中对其修改，无返回值】
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
row, col = len(grid2), len(grid2[0])
self.check = True
def DFS(x:int, y:int) -> int:
for nx ,ny in [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]:
if 0<=nx
DFS第二种：【这里用将check作为参数传入DFS中，并作为返回值】。这种方法其实不太好，因为每个递归DFS中都要开辟一个新的叫check的局部变量空间，这是没必要的。
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
row, col = len(grid2), len(grid2[0])
def DFS(x:int, y:int, check:bool) -> int:
for nx ,ny in [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]:
if 0<=nx
从计算时间和内存消耗来看，还是BFS的效果好。
总结
- 1.python的全局变量、局部变量
很有讲究，在函数内部一般是无法修改全局变量的
- 解决方法是：
【推荐】①用self.check作为可修改的全局变量：详见上面DFS第一种写法
②通过参数传入DFS函数：详见上面DFS第二种写法
python中函数的定义,调用，全局变量，局部变量，函数的嵌套使用-初级篇
