样例

Input:
11110
11010
11000
00000

Output: 1

算法1

(DFS) (flood fill) $O(mn)$

时间复杂度：参考wzc大佬题解，因为最多把每个格子遍历一次，因此为 $O(mn)$

• 遍历网格，遇到 ‘1’ 的时候深度优先遍历上下左右4个邻居，自己赋值 ‘0’, 说明此块陆地已经被遍历到。
• res 记录结果，在每次遇到 ‘1’ 的 dfs 入口加一。

算法2

并查集

@ CornerCao 题解
1. 第一次遍历网格，遇到 ‘1’ 时与上下左右4个邻居 union() 操作，即加入到一个同根的集合中。
2. 第二次遍历，遇到 ‘1’ 时检查 parent[i] == i ?, 只有并查集中的根节点满足这个条件，根结点的个数也就是答案需要的岛屿个数。

算法3

BFS

遍历网格，遇到 ‘1’ 的时候将此坐标入队并标记为 ‘0’ 表示已经遍历过。
典型BFS框架，每次取出一个坐标，检查上下左右四个邻居，将符合条件的邻居入队并标记为‘0’。
res 记录结果，在每次遇到 ‘1’ 的 bfs 入口加一。

时间复杂度

$O (n * m)$
n: grid 宽度
m: grid 长度

1. DFS

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int M = grid.length, N = grid[0].length;
        int res = 0;
        for (int row = 0; row < M; row++) {
            for (int col = 0; col < N; col++) {
                if (grid[row][col] == '1') {
                    res ++;
                    dfs(grid, row, col);
                }
            }
        }
        return res;
    }

    public void dfs(char[][] grid, int row, int col) {
        int M = grid.length, N = grid[0].length;
        if (row < 0 || row >= M || col < 0 || col >= N || grid[row][col] == '0')
            return;

        grid[row][col] = '0';

        int[] dx = new int[]{0, 1, 0, -1}, dy = new int[]{1, 0, -1, 0};
        for (int i = 0; i < 4; i++) {
            int x = row + dx[i], y = col + dy[i];
            dfs(grid, x, y);
        }
    }
}

2. Union Find

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length, n = grid[0].length;
        UnionFind uf = new UnionFind(m * n);
        //1 union find
        int[] dx = new int[] {0, 1, 0, -1}, dy = new int[] {1, 0, -1, 0};
        for (int row = 0; row < m; row ++) {
            for (int col = 0; col < n; col ++) {
                if (grid[row][col] == '1') {
                    for (int d = 0; d < 4; d ++) {
                        int x = row + dx[d], y = col + dy[d];
                        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                            uf.union(encode(row, col, n), encode(x, y, n));
                        }
                    }
                }
            }
        }
        //2 记录结果
        int res = 0;
        for (int row = 0; row < m; row ++) {
            for (int col = 0; col < n; col ++) {
                if (grid[row][col] == '1') {
                    int idx = encode(row, col, n);
                    if (uf.parent[idx] == idx) {
                        res ++;
                    }
                }
            }
        }

        return res;
    }

    public int encode(int row, int col, int colNum) {
        return (row * colNum + col);
    }
}
// 并查集模板
class UnionFind {
    int[] parent, rank;
    int count;

    public UnionFind(int num) {
        parent = new int[num];
        rank = new int[num];
        count = num;

        for (int i = 0; i < num; i ++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public void union(int p, int q) {
        int pp = find(p), pq = find(q);
        if (pp == pq) return;

        count --;

        if (rank[pp] > rank[pq]) {
            parent[pq] = pp;
        } else if (rank[pp] < rank[pq]) {
            parent[pp] = pq;
        } else {
            parent[pq] = pp;
            rank[pp] ++;
        }
    }

    public int find(int p) {
        if (parent[p] == p) {
            return p;
        }

        parent[p] = find(parent[p]);
        return parent[p];
    }

    public int getCount() {
        return this.count;
    }
}

3. BFS

class Solution {
    int M, N;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int islands = 0;
        M = grid.length;
        N = grid[0].length;
        for (int row = 0; row < M; row++) {
            for (int col = 0; col < N; col++) {
                if (grid[row][col] == '1') {
                    // flood fill by bfs
                    islands += 1;
                    bfs(grid, row, col);
                }
            }
        }
        return islands;
    }

    private void bfs(char[][] grid, int row, int col) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(row, col));
        grid[row][col] = '0';

        int[] dx = new int[] {0, 1, 0, -1}, dy = new int[] {1, 0, -1, 0};
        while (!q.isEmpty()) {
            Point cur = q.poll();
            for (int i = 0; i < 4; i++) {
                int x = cur.x + dx[i], y = cur.y + dy[i];
                if (x < 0 || x >= M || y < 0 || y >= N) continue;
                if (grid[x][y] == '0') continue;
                // enqueue valid neighbor Point
                q.offer(new Point(x, y));
                grid[x][y] = '0';
            }
        }
    }
}

class Point {
    int x;
    int y;
    Point (int x, int y) {
        this.x = x;
        this.y = y;
    }
}