dfs

遍历二维网格，如果网格值为“1”则以该网格为起点进行深度优先遍历，在搜索过程中值为1的网格都置为“0”。这样深度优先搜索的次数就是岛屿的数量。

class Solution {
    public int numIslands(char[][] grid) {
        int num = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int row = 0; row < rows; row++) 
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == '1') {
                    num++;
                    dfs(grid, row, col);
                }
            }
        return num;
    }

    private void dfs(char[][] grid, int row, int col) {
        grid[row][col] = '0';
        if (row - 1 >= 0 && grid[row - 1][col] == '1') dfs(grid, row - 1, col);
        if (row + 1 < grid.length && grid[row + 1][col] == '1') dfs(grid, row + 1, col);
        if (col - 1 >= 0 && grid[row][col - 1] == '1') dfs(grid, row, col - 1);
        if (col + 1 < grid[0].length && grid[row][col + 1] == '1') dfs(grid, row, col + 1);
    }
}

bfs

遍历二维网格，如果遇到值为1的网格则加入队列进行广度优先搜索，并将搜索过程中遇到的1变为0，这样广度优先搜索的次数就是岛屿的数量。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int num = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int row = 0; row < rows; row++) 
            for (int col = 0; col < cols; col++) {
                if (grid[row][col] == '1') {
                    num++;
                    grid[row][col] = '0';
                    Queue<Integer> queue = new LinkedList<>();
                    queue.offer(row * cols + col);
                    while (!queue.isEmpty()) {
                        int cur = queue.poll();
                        int x = cur / cols;
                        int y = cur % cols;
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            queue.offer((x - 1) * cols + y);
                            grid[x-1][y]= '0';
                        }
                        if (x + 1 < rows && grid[x + 1][y] == '1') {
                            queue.offer((x + 1) * cols + y);
                            grid[x+1][y]= '0';
                        }  
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            queue.offer(x * cols + y - 1);
                            grid[x][y-1]= '0';
                        }  
                        if (y + 1 < cols && grid[x][y + 1] == '1') {
                            queue.offer(x * cols + y + 1);
                            grid[x][y+1]= '0';
                        }
                    }
                }
            }
        return num;
    }
}

并查集

一开始所有值为1的方格为一个独立的连通分量，然后使用并查集对这些网格合并

class Solution {
    int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public int numIslands(char[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    for (int[] dir : dirs) {
                        int nx = dir[0] + i;
                        int ny = dir[1] + j;
                        if (nx >= 0 && nx < m && ny >=0 && ny < n && grid[nx][ny] == '1') {
                            uf.union(i * n + j, nx * n + ny);
                        }
                    }
                }
            }
        }
        return uf.getCount();
    }
    class UnionFind {
        int[] parent;
        int count;
        UnionFind(char[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            count = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        count++;
                    }
                }
            }
        }

        int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY)
                return;
            parent[rootX] = rootY;
            count--;
        }

        int getCount() {return count;}
    }
}