所以,在为下一场 ieextreme 比赛做准备时,我遇到了一些过去的问题。我发现一个真正困扰我的问题,因为我不知道该怎么做。我可能可以使用一些 300 行的暴力代码来实现它,但我我认为这不是在这样的比赛中应该做的事情,所以我需要你的帮助!
检测位图中的形状
问题陈述:在图像分析中,通常分析位图并观察其中存在的形状。对于此问题,设计一种算法来检测给定位图中的形状。地图中出现的形状应来自正方形、矩形、三角形和平行四边形集合。
在位图中,每个像素都表示为一个位,1 - 代表黑色,0 - 代表白色。参与者需要检测出黑色轮廓的形状。输入 第一行将包含位图的大小(以像素为单位),表示为(行,列)。
例如。 6,8 这意味着 6 行 8 列的位图。下一行将包含一系列从 0 到 255 的十进制数字,并用空格分隔。位图中的每个数字代表 8 个二进制位的集合。 IE。 55代表二进制模式00110111。
注意:位图中可以有多个形状,并且形状不得相交。然而,形状可以相互嵌套而没有任何交叉。
输出 位图中出现的形状按其名称的升序排列,并用逗号和空格分隔。例如。长方形、正方形、三角形
注意:输出末尾没有换行或空格 如果任何形状重复,则输出应包含与位图中一样多的重复。 IE。如果有 2 个正方形和 1 个三角形,则输出应为 Square、Square、Triangle
示例集 1
Input:
6 8
0 126 66 66 126 0
输出:矩形
示例集 2
Input:
6 16
0 0 120 120 72 144 73 32 123 192 0 0
输出:平行四边形、正方形
我编写了这段代码,以便我可以可视化位图并有 2 个列表(行和列中的位图)...
rows,cols=(int(i) for i in raw_input().split())
nums=[int(n) for n in raw_input().split()]
mr=[]
for i in range(0,len(nums),cols/8):
row=''
for j in range(i,i+cols/8):
b=bin(nums[j])[2:]
b='0'*(8-len(b))+b
row+=b
mr.append(row)
mc=[''.join([mr[i][j] for i in range(rows)]) for j in range(cols)]
谢谢您的时间...请用Python、C++或Ruby回答,因为这些是我能理解的语言,甚至是算法上的...