华为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）。

用例

题目解析

本题可以使用并查集。

有几个像素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("无"