目录
🍕题目
🍔方法一：BFS就是广度优先搜索
BFS就是广度优先搜索
先要记录初始节点的颜色值（找个变量存储起来）
1)我们从给定的起点开始，给它染色，进行广度优先搜索。这个初始节点当作第一层。
找到初始节点周围四个节点，给它们染色（符合条件的才能染），
2)这四个节点当作第二层。
再找到这四个节点周围八个节点，给它们染色（符合条件的才能染），
3)这八个节点当作第三层。
重复以往，层层递进，直到找不到符合要求的节点。
4)每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。
🍟BFS代码
class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]: currcolor = image[sr][sc] if currcolor == newColor: return image n,m = len(image),len(image[0]) que = collections.deque([(sr,sc)]) image[sr][sc] = newColor while que: x,y = que.popleft() for mx,my in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]: if 0 <= mx < n and 0 <= my < m and image[mx][my] == currcolor: que.append((mx,my)) image[mx][my] = newColor return image
🍔方法二：DFS
DFS，即
深度优先搜索。
1）先定个四个方向的顺序，例如上下左右，先上后下后左最后右
2）首先找到初始节点，给它染色。
3）按照方向的顺序，这里是上，就先把这个点的上方点先染色。
4）一直往上一直往上，直到不符合要求，便退一步，再找这个点的下方向
重复这个步骤。（这步是和BFS主要差别）
🍟代码
class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]: n, m = len(image), len(image[0]) currColor = image[sr][sc] def dfs(x: int, y: int): if image[x][y] == currColor: image[x][y] = newColor for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]: if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor: dfs(mx, my) if currColor != newColor: dfs(sr, sc) return image
🍕题目
🍔思路：
1）题目其实想让我们求网格中每个连通形状的面积，然后取最大值。（1表示岛屿）
2）如果我们在一个土地上，以 4个方向查找与之相连的每一个土地（以及与这些土地相连的土地）
，
那么探索过的土地总数将是该连通形状的面积。如同等于5 * 1 = 5
3）同时为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 0。这样我们就不会多次访问同一土地。
🍟代码
先定义dfs深度优先搜索函数，在定义一个求最大岛屿面积函数
具体见代码
class Solution: def dfs(self, grid, cur_i, cur_j) -> int: if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1: return 0 else:grid[cur_i][cur_j] = 0 #如果不是0，而且没越界就是岛屿的土地 ans = 1 for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: #不断探寻 next_i, next_j = cur_i + di, cur_j + dj ans += self.dfs(grid, next_i, next_j) return ans def maxAreaOfIsland(self, grid: List[List[int]]) -> int: ans = 0 for i, l in enumerate(grid): for j, n in enumerate(l): ans = max(self.dfs(grid, i, j), ans) #调用定义的dfs函数 return ans
