2013-07-03 81 views
0

我有一個「塊」(以2D數組的形式,可以是5 * 5,17 * 17或其他)的網格,我可以隨意添加或刪除塊, 除了爲中心,應該永遠在那裏。在網格中查找孤立的塊組

我可以放置塊,如果他們有一個本地鄰居:在他們的右/左/上/下(至少有一個)。

通過刪除一些塊,它可能會將其他塊隔離,但沒有「連接」到中心塊,我想避免這種情況。

我正在尋找一個快速解決方案,以檢查我的所有塊是否有連接到中心,最簡單的可能(就編碼而言,我可以接受有一個非最佳解決方案,因爲這應該是在非常小的數據上執行,而不是經常)。我腦海中想到的第一件事就是將其作爲路徑搜索來實現,但似乎過度。

我使用C++,但不應該有任何區別。

回答

1

您需要使用DFS/BFS查找連接的組件。創建初始圖形,並且在添加新塊時,可以添加新邊,或者在刪除塊時刪除邊。當您刪除塊時,刪除圖中的那些邊,並檢查它是否導致圖中的兩部分斷開。這很簡單,再次執行DFS。如果它不斷開,您可以刪除該塊。

DFS只有8行左右才能實現,對於小型數據集來說這很優雅。