#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 判断岛屿数量
# @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