class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        if (n == 0) return 0;
        
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private void bfs(char[][] grid, int i, int j) {
        int m = grid.length;
        if (m == 0) return;
        int n = grid[0].length;
        if (n == 0) return;
        
        int k = i * n + j;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(k);
        
        while (!queue.isEmpty()) {
            k = queue.poll();
            
            int x = k / n;
            int y = k % n;
            
            if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                k = (x - 1) * n + y;
                queue.offer(k);
                grid[x - 1][y] = '0';
            }
            if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                k = x * n + y - 1;
                queue.offer(k);
                grid[x][y - 1] = '0';
            }
            if (x + 1 < m && grid[x + 1][y] == '1') {
                k = (x + 1) * n + y;
                queue.offer(k);
                grid[x + 1][y] = '0';
            }
            if (y + 1 < n && grid[x][y + 1] == '1') {
                k = x * n + y + 1;
                queue.offer(k);
                grid[x][y + 1] = '0';
            }
        }
    }
}