岛问题

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛?

举例：
　　0 0 1 0 1 0

　　1 1 1 0 1 0

　　1 0 0 1 0 0

　　0 0 0 0 0 0
这个矩阵中有三个岛.

单CPU 单核解法：

 1 package my_basic.class_5;
 2 
 3 public class IslandNum {
 4     public static int islandCount(int[][] matrix) {
 5         if (matrix == null || matrix[0] == null) {
 6             return 0;
 7         }
 8         int N = matrix.length;
 9         int M = matrix[0].length;
10         int res = 0;
11         for (int i = 0; i < N; i++) {
12             for (int j = 0; j < M; j++) {
13                 if (matrix[i][j] == 1) {
14                     res++;
15                     infect(matrix,i,j,N,M);
16                 }
17             }
18         }
19         
20         return res;
21     }
22 
23     //递归函数  感染函数
24     private static void infect(int[][] m,int i, int j, int N, int M) {
25         if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {  //边界条件  i是从0开始的
26             return;
27         }
28         m[i][j] = 2;
29         infect(m, i+1, j, N, M);
30         infect(m, i-1, j, N, M);
31         infect(m, i, j-1, N, M);
32         infect(m, i, j+1, N, M);
33     }
34     
35     public static void main(String[] args) {
36         int[][] m1 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
37                         { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, 
38                         { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
39                         { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, 
40                         { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
41                         { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
42                         { 0, 0, 0, 0, 0, 0, 0, 0, 1 }, };
43         System.out.println(islandCount(m1));
44 
45         int[][] m2 = {  { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, 
46                         { 0, 1, 1, 1, 1, 1, 1, 1, 0 }, 
47                         { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
48                         { 0, 1, 1, 0, 0, 0, 1, 1, 0 }, 
49                         { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, 
50                         { 0, 0, 0, 0, 1, 1, 1, 0, 0 },
51                         { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
52         System.out.println(islandCount(m2));
53 
54     }
55 
56 }

如果是多CPU 并行解法，将矩阵任意切割成几个块，分别计算块中的岛数量；

把两个块合并的过程中，比较边界，用并查集实现；每一个岛有一个代表节点，

　　如果边界是1，但是不属于同一个集合，就按并查集合并集合，岛的数量 - 1；

　　属于同一个集合，就不用减了，这样防止多减的情况发生；

　　是0，继续往下走；