提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

【华为机试真题】图像物体的边界

2023-02-18 16:36:21 时间

题目描述

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

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

地图规格约束为：0<M<100;0<N<100

输入描述：

第一行，行数M，列数N

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

输出描述：

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

如果没有边界输出0（比如只存在像素1，或者只存在像素5）。

示例1

输入：

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

说明：与像素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

输入：

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的格子相邻的像素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）相邻。

题目解析

我理解题目意思是只有5周围一圈的1为边界，也就是直接与5相邻的点才认为是边界，如果边界间存在相邻（上，下，左，右，左上，左下，右上，右下），认为是同一个边界；

我们把上面的例子换个表示方式可能会更容易理解，我们将非边界的位置修改为0看看；

示例1：

1 1 1 0 0 0
1 5 1 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 1 1
0 0 0 0 1 5

左上角的像素矩阵与右下角的像素矩阵没有相邻，而示例2转换后是有相邻的，所以认为是1个边界，我们转换看下。

示例2：

1 1 1 0 0 0
1 5 1 0 0 0
1 1 1 0 0 0
0 0 0 1 1 1
0 0 0 1 5 1
0 0 0 1 1 1

方案1

那我们思考下这道题要怎么求解呢，首先我想到的是在矩阵中找到所有的5的左边，然后顺序检查周围的边界坐标，并记录下坐标点；

在判断下一个5周围的点，与之间每个矩阵判断是否相邻，有相邻合并边界集合；

这种方案的问题在于比较矩阵相邻，因为不是重合的点所以判断起来比较麻烦。

方案2

那我们换个思路再考虑下，如果两个5之间的距离小于等于4时，是不是就必然相邻了呢，这样我们只要能够获取到5的下标，并且两两求解距离，理论上是可行的。

两个方案相比，每个点从计算16个点的相邻变成了2个点的距离，大大减少了计算次数。

如何求两点之间的直线距离，直线距离就是两点之间水平距离的平方加上垂直距离的平方的和的平方根。

求平方根的两种方式：

import math

def do_distance(x1, y1, x2, y2):
    return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

# 如果不记得math的使用的方式
def do_distance(x1, y1, x2, y2):
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2)**0.5

这里需要注意，求解两点间的距离还不能适应这道题，（1，1）和（4，4）两点距离为4.242，而在两点间存在的只有两个加上两点本身，我们认为距离为4，是相邻的。

def do_distance(spot1, spot2):
    return (spot2[0] - spot1[0]) <= 3 \
           and (spot2[1] - spot1[1]) <= 3

参考代码

下面使用方案2求解下这道题

m, n = input().split()
map = [input().split() for _ in range(int(m))]

spot_aggs = []

for x in range(int(m)):
    for y in range(int(n)):
        if map[x][y] == '5':
            if not spot_aggs:
                spot_aggs.append({(x, y)})
                continue
            # 不相邻矩阵集合
            flg = False
            for agg in spot_aggs:
                # 和相邻矩阵中任意一个5相邻，加入这个集合
                for spot in agg:
                    if is_adjacent(spot, (x, y)):
                        agg.add((x, y))
                        flg = True
                        break
            # 和每个矩阵集合都不相邻，创建一个新集合
            if not flg:
                spot_aggs.append({(x, y)})

print(len(spot_aggs))

这里会有一个问题，先给个输入示例：

6 9
1 1 1 0 0 0 1 1 1
1 5 1 0 0 0 1 5 1
1 1 1 0 0 0 1 1 1
0 0 0 1 1 1 0 0 0
0 0 0 1 5 1 0 0 0
0 0 0 1 1 1 0 0 0

这个示例的输出应该是1，而上面的程序输出为2，在我们获取5时是从左到右，从上至下检查的，我们可以看到左上、右上、下三个点；

计算左上时还没有其他点，建立独立的集合；

计算右上，遍历集合此时与集合中的点都不相邻，建立独立的集合；

计算下这个点，遍历集合此时与两个集合中的点都相邻，分别加入两个集合，这时还需要合并着两个集合。

m, n = input().split()
map = [input().split() for _ in range(int(m))]

spot_aggs = []

for x in range(int(m)):
    for y in range(int(n)):
        if map[x][y] == '5':
            if not spot_aggs:
                spot_aggs.append({(x, y)})
                continue
            # 不相邻矩阵集合
            tmp = []
            for agg in spot_aggs:
                # 和相邻矩阵中任意一个5相邻，加入这个集合
                for spot in agg:
                    if is_adjacent(spot, (x, y)):
                        tmp.append(agg)
                        break
            if len(tmp) == 1:
                tmp[0].add((x, y))
            elif len(tmp) > 1:
                # 合并相邻集合
                new_agg = {(x, y)}
                for i in tmp:
                    new_agg.update(i)
                    spot_aggs.remove(i)
                spot_aggs.append(new_agg)
            else:
                # 和每个矩阵集合都不相邻，创建一个新集合
                spot_aggs.append({(x, y)})

print(len(spot_aggs))

最后，如果你有什么样的问题或解题心得，欢迎评论区交流！

相关文章