题解 | 岛屿数量

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组
# @return int整型
#
class Solution:
    def solve(self, grid: List[List[str]]) -> int:
        # write code here
        # 呃，之前那个方法超时了，还是老老实实BFS试试吧
        # 总体思路是这样的：
        # 在grid中找1，岛屿数量加1
        # 找到之后将其改为0（这个地方我没想到）
        # 然后拓展它的岛屿（这里想到了），将这个岛屿上的1都改为0
        # 那么如何拓展呢？
        # 构造一个队列dp，放置这个岛屿待遍历的点,也就是发散点
        # 对于dp中的一个点，提出来，并从dp中除去
        # 每次找其四个邻点，如果为1，那么就将这个邻点改为0，把这个邻点坐标放到dp里去
        # 如果为0，那就不用管
        # 这样循环，逐步将这个岛屿的所有点值消为0
        # 我想过这个拓展岛屿的思路，但觉得太麻烦了，也没想到改成0这点
        # 卡在拓展的过程中了
        # 知道要用队列，逐步拓展
        # 但就是细化不出来,主要就是没想到改成0这点
        # directions那里也可以借鉴，挺好使的
        from collections import deque

        if not grid or not grid[0]:
            return 0
        n, m = len(grid), len(grid[0])
        island_count = 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1":
                    island_count += 1
                    grid[i][j] = "0"
                    dp = deque([(i, j)])
                    while dp:
                        x, y = dp.popleft()
                        for dx, dy in directions:
                            nx, ny = x + dx, y + dy
                            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == "1":
                                grid[nx][ny] = "0"
                                dp.append((nx, ny))
        return island_count