計算位圖中「孔」的數量

考慮單元爲0或1的MxN位圖。'1'表示填充，'0'表示空。計算位圖中「孔」的數量

找到位圖中「孔」的數量，其中孔是空單元的連續區域。

例如，這有兩個孔：

...這隻有一個：

什麼是最快的方法，當M和N均爲1之間8？

說明：對角線不被認爲是連續的，只有旁邊的問題。

注意：我正在尋找利用數據格式的東西。我知道如何將其轉換爲圖形和[BD] FS，但似乎過度殺傷。

來源

2010-10-26 florin

爲什麼這樣的功課或代碼高爾夫的氣味？ @弗洛林，感謝您的更新。請考慮這個評論「廢除」。我們會接受你的話。 – jcolebrand 2010-10-26 16:59:46

它就像功課！ – Luiscencio 2010-10-26 17:00:55

這不是作業，但沒關係。我試圖解決更大的問題，這只是一個子問題。 – florin 2010-10-26 17:02:05

您需要對圖像做connected component labeling。您可以使用上面鏈接的維基百科文章I中描述的Two-pass algorithm。鑑於你的問題的小尺寸，One-pass algorithm就足夠了。

你也可以使用BFS/DFS但我建議上述算法。

來源

2010-10-26 17:01:22 Jacob

是的，連接組件標籤應該做到這一點。另外，祝賀10k，@Jacob（或者幾乎 - 我想你今天已經達到了上限）。 – Jonas 2010-10-26 18:00:57

@Jonas：我知道！希望弗羅林今天能夠接受這個答案:) – Jacob 2010-10-26 19:02:27

@Jonas：我現在可以承認這些祝賀：D – Jacob 2010-10-26 22:03:35

這似乎是一個很好的使用不相交集數據結構。
通過每個元件轉換的位圖的2D陣列
環
如果當前元素是0，所設置的一個其「之前的」空的鄰居（已經訪問過）
的合併它，如果它不具有空的鄰居，將其添加到自己的一套

然後就指望套

數量

來源

2010-10-26 17:07:44

〜這正是@Jacob已經鏈接到的東西。 – jcolebrand 2010-10-26 17:23:29

我在看過他之前寫了這個答案。 – 2010-10-26 17:26:47

有可能是通過使用表查找和位運算獲得優勢。

例如，可以在256個元素表中查找8個像素的整行，因此單個查找可以獲得1×N的字段中的空洞數量。然後可能會有一些256xK元素的查找表，其中K是前一行中孔配置的數量，包含完整孔的數量和下一個孔配置。這只是一個想法。

來源

2010-10-26 19:36:14 Vovanium

我剛剛開始構建我的2^64查找表，但是我用完RAM 8的一年預算^^ – florin 2010-10-26 21:07:28

弗洛林：使用分佈式計算！ =） – Vovanium 2010-10-26 21:14:24

我發現這個謎題非常有趣，我花了一些空閒時間，使用560字節的表格（適用於8位寬模式），使用查找和按位操作來製作'逐行'算法草圖。這裏是代碼：http://dl.dropbox.com/u/13343791/holecount2.c對不起，如果代碼沒有很好的記錄。 – Vovanium 2010-11-03 12:14:51

計算位圖中「孔」的數量

回答

相關問題