华为OD统一考试 - 图像物体的边界

题目描述

给定一个二维数组M行N列,二维数组里的数字代表图片的像素,为了简化问题,仅包含像素1和5两种像素,每种像素代表一个物体,2个物体相邻的格子为边界,求像素1代表的物体的边界个数。

像素1代表的物体的边界指与像素5相邻的像素1的格子,边界相邻的属于同一个边界,相邻需要考虑8个方向(上,下,左,右,左上,左下,右上,右下)。

其他约束

地图规格约束为:

0<M<100

0<N<100

1)如下图,与像素5的格子相邻的像素1的格子(0,0)、(0,1)、(0,2)、(1,0)、(1,2)、(2,0)、(2,1)、(2,2)、(4,4)、(4,5)、(5,4)为边界,另(0,0)、(0,1)、(0,2)、(1,0)、(1,2)、(2,0)、(2,1)、(2,2)相邻,为1个边界,(4,4)、(4,5)、(5,4)相邻,为1个边界,所以下图边界个数为2。

2)如下图,与像素5的格子相邻的像素1的格子(0,0)、(0,1)、(0,2)、(1,0)、(1,2)、(2,0)、(2,1)、(2,2)、(3,3)、(3,4)、(3,5)、(4,3)、(4,5)、(5,3)、(5,4)、(5,5)为边界,另这些边界相邻,所以下图边界个数为1。

注:(2,2)、(3,3)相邻。

输入描述

第一行,行数M,列数N

第二行开始,是M行N列的像素的二维数组,仅包含像素1和5

输出描述

像素1代表的物体的边界个数。

如果没有边界输出0(比如只存在像素1,或者只存在像素5)。

用例

输入

6 6

1 1 1 1 1 1

1 5 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 5

输出

2

说明

参考题目描述部分

输入

6 6

1 1 1 1 1 1

1 5 1 1 1 1

1 1 1 1 1 1

1 1 1 1 1 1

1 1 1 1 5 1

1 1 1 1 1 1

输出

1

说明

参考题目描述部分

题目解析

本题可以使用并查集。

有几个像素5,我们就可以先假设有几个不相邻的边界。

 而判断两个边界相邻的条件是:两个像素5坐标满足:|x1-x2| <=3 && |y1-y2| <=3

即如上图绿色线就是另一个像素5的移动范围边界。

因此,本题可以转化为求解像素5是否联通的并查集求解。

因为本题要求解的是:像素1代表的物体的边界个数。我们可以看一个例子:

上图所示,应该存在几个边界呢?

如果按照前面思路,则只有1个边界。前面思路其实是以像素5为核心,将像素5周围的像素1统一视为一个边界,但是这是不符合题意的,因为题目要求说:

像素1代表的物体的边界指与像素5相邻的像素1的格子,边界相邻的属于同一个边界

而上面图示中,两个像素1格子是不相邻的,因此不能算同一边界。

我的解题思路如下:

首先,遍历矩阵,将所有像素5相邻的像素1(边界)坐标都取出来。

然后,利用并查集,对这些边界像素1格子进行合并,合并规则是:

两个格子的横向、纵向距离均小于等于1,即为相邻,即可合并。

import Foundation

func ODTest_2_20() {
    print("输入描述")
    print("第一行,行数M,列数N")
    // 矩阵 [行数, 列数]
    let MN = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    if MN.count != 2 {
        print("无"

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024华为OD机试卷题 文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。

全部评论

相关推荐

真烦好烦真烦:牛友太有实力了
点赞 评论 收藏
分享
05-24 14:12
门头沟学院 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务