Bought some FAZ and SMN this morning - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

Bought some FAZ and SMN this morning

Bought some FAZ and SMN this morning# Stock

L*g2010-02-05 08:02

1 楼

给一个bmp图片，只有黑白两色，照得是某公司生产的橡皮筋（黑色），背景白色。要
求算法判断橡皮筋是否合格（闭环）。开环的当然是不合格的。提示：圆型，方形，8
字形，月牙形的橡皮筋都合格，无论粗细。
有点难，本人觉得1个小时写不出代码，只能讲讲算法思路：图的遍历，把背景填充成
其他颜色，这样橡皮筋圈起来的部分就仍是白色。判断bmp是2种颜色（不合格）还是3
种颜色（合格）。

p*92010-02-05 08:02

2 楼

test water

h*d2010-02-05 08:02

3 楼

断了如果有重叠也可以有圈起来的部分吧。

8
3

【在 L*********g 的大作中提到】

: 给一个bmp图片，只有黑白两色，照得是某公司生产的橡皮筋（黑色），背景白色。要
: 求算法判断橡皮筋是否合格（闭环）。开环的当然是不合格的。提示：圆型，方形，8
: 字形，月牙形的橡皮筋都合格，无论粗细。
: 有点难，本人觉得1个小时写不出代码，只能讲讲算法思路：图的遍历，把背景填充成
: 其他颜色，这样橡皮筋圈起来的部分就仍是白色。判断bmp是2种颜色（不合格）还是3
: 种颜色（合格）。

x*i2010-02-05 08:02

4 楼

这个不行吧，比如说8上面的那个圈圈有个缺口，还是会有3个颜色。
如果黑点的黑色邻居数是奇数，就是断了.这样似乎可以

L*g2010-02-05 08:02

5 楼

想的太复杂了。:-) 一小时不是能写个大工程的。
只求是否闭环(closed loop)。 "断了如果有重叠也可以有圈起来的部分吧": 这算闭环。
挺好玩的题。

v*a2010-02-05 08:02

6 楼

这就是求出无向图中的闭环吧，将黑色的点用图表述，即对于每个顶点，如果该顶点的
度小于或等于1，将该顶点和相连的边放入set V.并将另外与这些边相关的其它顶点的
度减1. 重复对剩下的度数变为1的顶点进行操作。
如果图中还剩下顶点及边，说明有闭环。
如果set V中有顶点，说明有断头（比如8上面的圈有缺口）。
如果图中没有顶点，说明无环。