华为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("无")
        return
    }
    let M = MN[0], N = MN[1]
    // 矩阵
    print("第二行开始，是M行N列的像素的二维数组，仅包含像素1和5")
    var matrix = Array(repeating: Array(repeating: 0, count: N), count: M)
    for i in 0 ..< M {
        matrix[i] = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    }

    print("像素1代表的物体的边界个数。")
    print("如果没有边界输出0（比如只存在像素1，或者只存在像素5）。")

    // 上、下、左、右、左上、左下、右上、右下的横坐标、纵坐标偏移量
    let offsets = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]]
    // 记录所有边界位置
    var brands: Set<Int> = []
    for i in 0 ..< M {
        for j in 0 ..< N {
            if matrix[i][j] == 5 {
                offsets.forEach { offset in
                    let newI = i + offset[0]
                    let newJ = j + offset[1]
                    if newI >= 0 && newI < N && newJ >= 0 && newJ < N && matrix[newI][newJ] == 1 {
                        brands.insert(newI * N + newJ)
                    }
                }
            }
        }
    }

    let brandsList = Array(brands)
    let k = brandsList.count
    let ufs = UnionFindSet(k)

    for i in 0 ..< k {
        let x1 = brandsList[i] / N
        let y1 = brandsList[i] % N
        for j in 0 ..< k {
            let x2 = brandsList[j] / N
            let y2 = brandsList[j] % N

            // 如果两个边界像素1的位置 横向、纵向距离均小于1，则相邻，可以进行合并
            if abs(x1 - x2) <= 1 && abs(y1 - y2) <= 1 {
                ufs.union(i, j)
            }
        }
    }

    print("\(ufs.count)")

    class UnionFindSet {
        var fa: [Int]
        var count: Int

        init(_ n: Int) {
            count = n
            fa = Array(repeating: 0, count: n)
            for i in 0 ..< n { fa[i] = i }
        }

        func find(_ x: Int) -> Int {
            if x != fa[x] {
                fa[x] = find(fa[x])
                return fa[x]
            }
            return x
        }

        func union(_ x: Int, _ y: Int) {
            let x_fa = find(x)
            let y_fa = find(y)
            if x_fa != y_fa {
                fa[y_fa] = x_fa
                count -= 1
            }
        }
    }
}