岛的问题

发表于 阅读次数：

问题

leetcode-200岛屿数量

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例1：

输入:
11110
11010
11000
00000

输出: 1

示例 2:

输入:
11000
11000
00100
00011

输出: 3

思路

我们把题目改变一下帮助我们理解。

  • 有一种超级病毒，能在特定区域传播，这里我们用1代表可感染区域，把2代表已感染区域，把0代表不会感染的区域。我们把一个连在一起的感染区域称作一个感染区。
    • 问：现在病毒来袭，请计算会有几个感染区。

我们遍历矩阵，只要遇到可感染的情况1就进入递归，对其四个方向查找是否可继续感染1，把途径的1标记为已感染2。而后完成整个递归后感染区加1。继续遍历矩阵，直至结束。

下面来看下实际代码。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public static int countIslands(int[][] m){

        if(m == null || m.length == 0)
            return 0;
        int row = m.length;
        int column = m[0].length;
        int count = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < column; j++) {
                if(m[i][j] == 1) {
                    count ++;
                    infect(m, i, j, row, column);
                }
            }
        }
        return count;
    }

    private static void infect(int m[][], int i, int j, int N, int M) {

        //越界和不为1就代表不能感染或者已经感染
        if(i < 0 || j < 0 || i >= N || j >= M || m[i][j] != 1) {
            return;
        }
        m[i][j] = 2;
        //上下左右找可以感染的
        infect(m, i , j - 1, N, M);
        infect(m, i , j + 1, N, M);
        infect(m, i - 1, j, N, M);
        infect(m, i + 1, j, N, M);
    }
    
    public static void main(String[] args) {
        int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 0, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 0, 0, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m1));

        int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                { 0, 1, 1, 1, 1, 1, 1, 1, 0 },
                { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
                { 0, 1, 1, 0, 0, 0, 1, 1, 0 },
                { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
                { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
        System.out.println(countIslands(m2));
    }

补充：巧用并查集

上面那个解法十分的友好，但在数据量大的时候，那样的解是不可行的。
当数据大的需要用分布式计算的时候常常会把一大块进行分治，这之中有个大问题

当中间区域出现相连的情况，会有重复计算的情况

这时候并查集就可以登场了！！！

  1. 分布式算出各个感染区：把并且每个感染去独立作为一个集合，其根节点为开始感染的节点，算出总数。
  2. 合并：找出两两相连的两条边界，遍历其中一条，当有两个相邻节点都是感染时，判断他们是否为同一集合。
    • 若不同则总数-1，而后把用并查集union这两个节点。
    • 若相同或者均不为感染区，则跳过。

看个图理解一哈：

在分布式的情况下把感染区A、B、C三个集合(根节点可以取第一个感染节点)

  • 还有的情况兄弟萌可以自己画一下图（若有两个感染区，两次相邻，我们只会减去1个）

这里仅提供思路，扩展一下并查集的用途。请各位海涵。