class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        DIRS = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        color = 2
        def dfs(row, col):
            if grid[row][col] == "0":
                return
            # print(row, col)

            grid[row][col] = color
            for d in DIRS:
                # print(d[0], d[1])
                row_nxt = row + d[0]
                col_nxt = col + d[1]
                if row_nxt < 0 or row_nxt >= len(grid) or col_nxt < 0 or col_nxt >= len(grid[0]) or int(grid[row_nxt][col_nxt]) > 1:
                    continue
                dfs(row_nxt, col_nxt)
        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == "1":
                    # print(row, col)
                    dfs(row, col)
                    color +=1
        print(grid)
        return color - 2

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        DIRS = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        def dfs(i: int, j: int) -> None:
            # 出界，或者不是 '1'，就不再往下递归
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
                return
            grid[i][j] = '2'  # 插旗！避免来回横跳无限递归
            for d in DIRS:
                nxt_row = i + d[0]
                nxt_col = j + d[1]
                dfs(nxt_row, nxt_col)

        ans = 0
        for i, row in enumerate(grid):
            for j, c in enumerate(row):
                if c == '1':  # 找到了一个新的岛
                    dfs(i, j)  # 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
                    ans += 1
        return ans