数房子

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 5,822评论 0 19
  • 因为之前就复习完数据结构了,所以为了保持记忆,整理了一份复习纲要,复习的时候可以看着纲要想具体内容。 树 树的基本...
    牛富贵儿阅读 7,012评论 3 10
  • 课程介绍 先修课:概率统计,程序设计实习,集合论与图论 后续课:算法分析与设计,编译原理,操作系统,数据库概论,人...
    ShellyWhen阅读 2,362评论 0 3
  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,355评论 0 25
  • 孩子他妈打电话诉苦说:你看看你家这老二,怎么这么调皮捣蛋,到底像谁呀? 我一阵无语,虽说老二长的特像我,但性格不一...
    吉古吉阅读 216评论 0 1