200. Number of Islands (M)

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000
Output: 1

Example 2:

Input:
11000
11000
00100
00011
Output: 3

题意

给定一个只包含’1’和’0’的二维数组，’1’通过与上下左右四个方向毗邻的’1’相连组成岛屿，判断这样的岛屿有多少个。

思路

问题实际上可以转化为求连通分量的个数，可以使用DFS(BFS)或者并查集处理。

代码实现 - DFS

class Solution {
    int[] iPlus = {-1, 0, 1, 0};
    int[] jPlus = {0, -1, 0, 1};
    int m, n;
    boolean[][] visited;
    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int count = 0;
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j) {
        visited[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int adjI = i + iPlus[k], adjJ = j + jPlus[k];
            if (isValid(adjI, adjJ) && !visited[adjI][adjJ] && grid[adjI][adjJ] == '1') {
                dfs(grid, adjI, adjJ);
            }
        }
    }
    private boolean isValid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}

代码实现 - 并查集

class Solution {
    int[] iPlus = {1, 0};
    int[] jPlus = {0, 1};
    int m, n;
    int[] root;
    int count;
    public int numIslands(char[][] grid) {
            if (grid.length == 0) {
                return 0;
            }
        m = grid.length;
        n = grid[0].length;
        root = new int[m * n];
        for (int i = 0; i < m * n; i++) {
            root[i] = -1;
        }
        // 先初始化root数组和只有一个元素的连通分量的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    int index = changeIndex(i, j);
                    root[index] = index;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    int x = changeIndex(i, j);
                    // 搜索时只需要处理右侧和下方相邻的点
                    for (int k = 0; k < 2; k++) {
                        int adjI = i + iPlus[k], adjJ = j + jPlus[k];
                        if (isValid(adjI, adjJ) && grid[adjI][adjJ] == '1') {
                            int y = changeIndex(adjI, adjJ);
                            connect(x, y);
                        }
                    }
                }
            }
        }
        return count;
    }
    private int findRoot(int x) {
        int r = x;
        while (root[r] != r) {
            r = root[r];
        }
        // 路径压缩
        while (x != r) {
            int temp = root[x];
            root[x] = r;
            x = temp;
        }
        return r;
    }
    private void connect(int i, int j) {
        int iRoot = findRoot(i);
        int jRoot = findRoot(j);
        if (iRoot == jRoot) {
            return;
        }
        root[iRoot] = jRoot;
        count--;
    }
    private boolean isValid(int i, int j) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    // 二维坐标转化为一维坐标
    private int changeIndex(int i, int j) {
        return i * n + j;
    }
}