# 不修改输入参数
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.dx = [-1, 1, 0, 0]
        self.dy = [0, 0, 1, -1]
        if not grid or not grid[0]: return 0
        self.max_x = len(grid)
        self.max_y = len(grid[0])
        self.grid = grid

        self.visited = set()

        # return sum([self.floodfill_dfs(i, j) for i in range(self.max_x) for j in range(self.max_y)])
        return sum([self.floodfill_bfs(i, j) for i in range(self.max_x) for j in range(self.max_y)])

    def floodfill_dfs(self, x, y):
        if not self._is_valid(x, y):
            return 0
        self.visited.add((x, y))
        for k in range(4):
            self.floodfill_dfs(x + self.dx[k], y + self.dy[k])
        return 1

    def floodfill_bfs(self, x, y):
      if not self._is_valid(x, y):
        return 0

      self.visited.add((x, y))
      queue = collections.deque()
      queue.append((x, y))

      while queue:
        cur_x, cur_y = queue.popleft()
        for i in range(4):
          new_x, new_y = cur_x + self.dx[i], cur_y + self.dy[i]
          if self._is_valid(new_x, new_y):
            self.visited.add((new_x, new_y))
            queue.append((new_x, new_y))
      return 1


    def _is_valid(self, x, y):
        if x < 0 or x >= self.max_x or y < 0 or y >= self.max_y:
            return False
        if self.grid[x][y] == '0' or ((x, y) in self.visited):
            return False
        return True

# 修改输入参数
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

      islands = 0
      for i in range(len(grid)):
        for j in range(len(grid[i])):
          if grid[i][j] == '1': 
            islands += 1
            self.sink(grid, i, j)

      return islands

    def sink(self, grid, i, j):
      # terminator
      if grid[i][j] == '0':
        return 0

      # i,j == '1'
      grid[i][j] = '0'


      # ds = [[-1, 0], [0, -1], [1, 0], [0, 1]]
      # for d in ds:
      #  x = i + d[0]
      #  y = j + d[1]
      #  if 0 <= x < len(grid) and 0 <= y < len(grid[i]):
      #    if grid[x][y] == '1': 
      #      self.sink(grid, x, y)

      dx = [-1, 1, 0, 0]
      dy = [0, 0, -1, 1]
      for k in range(len(dx)):
        x = i + dx[k]
        y = j + dy[k]
        if 0 <= x < len(grid) and 0 <= y < len(grid[i]):
          if grid[x][y] == '1': 
            self.sink(grid, x, y)

class Solution {
    public int numIslands(char[][] grid) {

        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    sink(grid, i, j);
                }
            }
        }
        return result;
    }

    private void sink(char[][] grid, int i, int j) {

        if (grid[i][j] == '0') return;
        grid[i][j] = '0';

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int k = 0; k < dx.length; k++) {

            int x = i + dx[k];
            int y = j + dy[k];

            if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
                if (grid[x][y] == '0') continue;
                sink(grid, x, y);
            }
       }
    }
}

# 光头哥
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def sink(i, j):
            if 0 <= i < len(grid) and 0 <= j < len(grid[i]) and grid[i][j] == '1':
                grid[i][j] = '0'
                list(map(sink, (i + 1, i - 1, i, i), (j, j, j + 1, j - 1)))
                return 1
            return 0

        return sum(sink(i, j) for i in range(len(grid)) for j in range(len(grid[i])))

class UnionFind(object):
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.count = 0
        self.parent = [-1] * (m * n)
        self.rank = [0] * (m * n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self.parent[i * n + j] = i * n + j
                    self.count += 1

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)

        if rootx != rooty:
            if self.rank[rootx] > self.rank[rooty]:
                self.parent[rooty] = rootx
            elif self.rank[rootx] < self.rank[rooty]:
                self.parent[rootx] = rooty
            else:
                self.parent[rooty] = rootx
                self.rank[rootx] += 1
            self.count -= 1

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0

        uf = UnionFind(grid)
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        m, n = len(grid), len(grid[0])

        for i in range(m): 
            for j in range(n):
                if grid[i][j] == '0':
                    continue;
                for d in directions:
                    nr, nc = i + d[0], j + d[1]
                    if nr >= 0 and nc >= 0 and nr < m and nc < n and grid[nr][nc] == '1':
                        uf.union(i * n + j, nr * n + nc)

        return uf.count