第三題：線段辨認

問題敘述

在某個工程領域的應用當中，工程是用相機拍下了某些工業影像。這些影像由

黑點與白點所組成。在下圖中，我們展示了其中的一幅工業影像。

------A-----H--------

------X-----X--------

------X-----X--------

E-----B-----IXXXXXXXJ

-X-----X-------------

--G-----X------------

-X---K---CXXXXXXXXXXD

F----LM--------------

圖1 一張工業用影像

在圖1中，”-“ 代表白點，”X” 代表黑點。在這種影像中會有許多線條。這些線

條都是由許多線段所組成。所謂的線段是有兩個端點的直線而且長度必須大於等

於3。例如，圖1 中，我們特地將幾個線段的端點用ABC 標示出來。點A 到點B

是一個線段，最後點B 到點C 也是一個線段。在圖1 的影像中，總共有A-B, B-C,

C-D, E-G, G-F, H-I, I-J 等七個線段。圖中還有一團黑點KLM。這一團黑點理

論上可以形成3 個線段K-L,K-M,以及L-M。不過因為他們的長度都小於3,所以

不能稱之為線段。

給你一個工業影像，請寫一個程式判斷總共有多少線段。

注意事項：

測試資料中的線段，一定是垂直，水平或者是45 度角的線段。另外沒有任何

兩條線條會交叉。也就是說任何一個線段頂點頂多屬於兩個線段。