/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  const dfs = (i, j) => {
    // i, j 表示当前坐标
    grid[i][j] = '-1'
    for (const [x, y] of [
      [i + 1, j],
      [i - 1, j],
      [i, j + 1],
      [i, j - 1],
    ]) {
      if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length) {
        // 越界条件判断
        if (grid[x][y] !== '-1' && grid[x][y] !== '0') {
          // 访问过和水判断
          dfs(x, y)
        }
      }
    }
  }
  let ans = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        // 新岛屿
        dfs(i, j)
        ans += 1
      }
    }
  }
  return ans
}

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