为了规划城市，需要统计房屋数目信息。方法如下，一张航拍照片会被分隔为M*N个小格子，用数字0或1分别表示某格子看到的是空地还是屋顶，相邻的屋顶属于同一栋房子，位于对角线上的屋顶不属于同一栋房子（这也符合实际），现在先输入航拍照片的大小（M行N列），再输入矩形俯视图的布局，要求我们输出这块矩形空地中有多少栋房子
Input：
5 5
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
Expected Return Value：
1
Input：
5 6
1 1 0 0 1 0
0 1 1 1 0 0
1 0 0 1 0 0
0 0 0 0 1 1
0 0 0 0 1 1
Expected Return Value：
4
用DFS递归求解本题，扫描矩阵的每一个元素，以发现的屋顶为起点向四个方向进行DFS递归感染（这里置0），每一个感染过程所遇到的所有屋顶都属于同一栋房子，所以仅需在感染过程开始前对房子进行一次计数，这样遍历一遍矩阵就可得到房子的数目，时间复杂度O(M * N)，代码如下：
public class CountHourse {
public static int countHourse(int[][] matrix) {
if (matrix == null || matrix[0] == null) {
return 0;
}
int row = matrix.length;
int col = matrix[0].length;
int count = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 1) {
count++; // 发现屋顶，房子数增加
infect(matrix, i, j); // 以发现的屋顶为起点向四个方向进行DFS递归感染
}
}
}
return count;
}
/**
* 以matrix[i][j]为起点向四个方向进行DFS递归感染
*
* @param i
* @param j
* @param matrix
*/
public static void infect(int[][] matrix, int i, int j) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
return;
}
if (matrix[i][j] == 1) {
matrix[i][j] = 0; // 感染当前结点
infect(matrix, i - 1, j); // 向上方递归感染
infect(matrix, i + 1, j); // 向下方递归感染
infect(matrix, i, j - 1); // 向左方递归感染
infect(matrix, i, j + 1); // 向右方递归感染
}
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int row = scan.nextInt();
int col = scan.nextInt();
int[][] matrix = new int[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
matrix[i][j] = scan.nextInt();
}
}
System.out.println(countHourse(matrix));
}
scan.close();
}
}
进阶：如果可以使用并行计算，如何来设计你的算法？
利用分治的思想，根据CPU个数将整个矩阵分成若干个子矩阵，让每个CPU遍历子矩阵并进行递归感染，对于每个结点都记录下把它感染的感染源结点，让这些结点与它们的感染源结点一起构成一个并查集，感染源结点作为并查集代表。待各CPU遍历完对应的子矩阵，再对子矩阵构造出的并查集进行合并，即合并两个子矩阵边界上相邻且均为1的两个元素所在的并查集，待所有子矩阵合并完毕，统计整个矩阵中并查集的个数，即为总的房子数。
