华为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)。
用例
输入 |
|
输出 | 2 |
说明 | 参考题目描述部分 |
输入 |
|
输出 | 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("无") 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 } } } }
本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。