数房子

为了规划城市，需要统计房屋数目信息。方法如下，一张航拍照片会被分隔为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的两个元素所在的并查集，待所有子矩阵合并完毕，统计整个矩阵中并查集的个数，即为总的房子数。