在網格中查找孤立的塊組

Question

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

我可以放置塊，如果他們有一個本地鄰居：在他們的右/左/上/下（至少有一個）。

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

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

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

Answer 1

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

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