231-1374-Number of Islands.py

## https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1374/
import queue


class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        MOVEMENTS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        row, col = len(grid), len(grid[0])

        def avail(i: int, j: int) -> bool:
            return True if 0 <= i < row and 0 <= j < col else False

        def dfs_zero_out(i: int, j: int):
            if avail(i, j) and grid[i][j] == "1":
                grid[i][j] = "0"
                for di, dj in MOVEMENTS:
                    dfs_zero_out(i + di, j + dj)

        def bfs_zero_out(i: int, j: int):
            grid[i][j] = "0"
            q = queue.Queue()
            q.put((i, j))

            while not q.empty():
                ci, cj = q.get()
                for di, dj in MOVEMENTS:
                    ii, jj = ci + di, cj + dj
                    if avail(ii, jj) and grid[ii][jj] == "1":
                        q.put((ii, jj))
                        grid[ii][jj] = "0"

        num = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
#                     dfs_zero_out(i,j)
                    bfs_zero_out(i, j)
                    num += 1
        return num