二维矩阵中1所构成的块个数（孤岛问题）—头条笔试题

问题

给定一个二维数组，数组中仅包含0和1，上下左右和对角线相连的1构成一个块，求该二维数组中块的个数。 例如： input： 3 1 0 1 1 1 0 1 0 1 output：2(最后一个1构成一个单独的块)

思路

（1）采用深度优先搜索，遍历1在数组中的位置，对于遍历得到的1，先将其置位0再递归遍历该位置周围8个方向上是否为1，如果为1将其值变为0。这样顺次得到的1的个数就为最终结果； （2）标注法：用count变量标注块的编号。从左到右从上到下遍历数组，对于值为1的位置，如果其左上，上，右上，左都为0，那么该位置的值变为count+1;否则该位置的值变为其左上，上，右上，左位置的值。最后根据count就可以求得块的个数。 （3）通过并查集解决； 上面方法的时间复杂度都为O(n)

实现

// 下面通过DFS的方式实现 import java.util.*; public class TT2 { public static void DFS(int[][] flag , int i, int j, int n, int m){ flag[i][j] = 0; // int lenRow = flag.length; // int lenCol = flag[0].length; // 左上 if((i - 1) >= 0 && (j - 1) >= 0 && flag[i-1][j-1] == 1){ DFS(flag, i-1, j-1, n, m); } // 上 if((i - 1) >= 0 && flag[i-1][j] == 1){ DFS(flag, i-1, j, n, m); } // 右上 if((i - 1) >= 0 && (j + 1) < m && flag[i-1][j+1] == 1){ DFS(flag, i-1, j+1, n , m); } // 左 if((j - 1) >= 0 && flag[i][j-1] == 1){ DFS(flag, i, j-1,n, m); } // 右 if( (j + 1) < m && flag[i][j+1] == 1){ DFS(flag, i, j+1,n, m); } // 左下 if((i + 1) < n && (j - 1) >= 0 && flag[i+1][j-1] == 1){ DFS(flag, i+1, j-1,n, m); } // 下 if((i + 1) < n && flag[i+1][j] == 1){ DFS(flag, i+1, j,n, m); } // 右下 if((i + 1) < n && (j + 1) < m && flag[i+1][j+1] == 1){ DFS(flag, i+1, j+1,n, m); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int m = in.nextInt(); int[][] flag = new int[n][m]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j ++){ flag[i][j] = in.nextInt(); } } int count = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j ++){ if(flag[i][j] == 1){ count ++; DFS(flag, i, j, n, m); } } } System.out.println(count); } }