L*********g
发帖数: 8 | 1 给一个bmp图片，只有黑白两色，照得是某公司生产的橡皮筋（黑色），背景白色。要
求算法判断橡皮筋是否合格（闭环）。开环的当然是不合格的。提示：圆型，方形，8
字形，月牙形的橡皮筋都合格，无论粗细。
有点难，本人觉得1个小时写不出代码，只能讲讲算法思路：图的遍历，把背景填充成
其他颜色，这样橡皮筋圈起来的部分就仍是白色。判断bmp是2种颜色（不合格）还是3
种颜色（合格）。 |
h*d
发帖数: 19309 | 2 断了如果有重叠也可以有圈起来的部分吧。
8
3
【在 L*********g 的大作中提到】
: 给一个bmp图片，只有黑白两色，照得是某公司生产的橡皮筋（黑色），背景白色。要
: 求算法判断橡皮筋是否合格（闭环）。开环的当然是不合格的。提示：圆型，方形，8
: 字形，月牙形的橡皮筋都合格，无论粗细。
: 有点难，本人觉得1个小时写不出代码，只能讲讲算法思路：图的遍历，把背景填充成
: 其他颜色，这样橡皮筋圈起来的部分就仍是白色。判断bmp是2种颜色（不合格）还是3
: 种颜色（合格）。
|
x*******i
发帖数: 26 | 3 这个不行吧， 比如说8上面的那个圈圈有个缺口，还是会有3个颜色。
如果黑点的黑色邻居数是奇数，就是断了.这样似乎可以 |
L*********g
发帖数: 8 | 4 想的太复杂了。:-) 一小时不是能写个大工程的。
只求是否闭环(closed loop)。 "断了如果有重叠也可以有圈起来的部分吧": 这算闭环。
挺好玩的题。 |
v****a
发帖数: 236 | 5 这就是求出无向图中的闭环吧，将黑色的点用图表述，即对于每个顶点，如果该顶点的
度小于或等于1，将该顶点和相连的边放入set V.并将另外与这些边相关的其它顶点的
度减1. 重复对剩下的度数变为1的顶点进行操作。
如果图中还剩下顶点及边，说明有闭环。
如果set V中有顶点，说明有断头（比如8上面的圈有缺口）。
如果图中没有顶点，说明无环。 |
