快速算法在棋盤上清除棋盤

我目前正在編寫一些代碼來處理棋盤。 Go板被表示爲一系列顏色。該陣列具有size×size條目並且代表二維方形板。快速算法在棋盤上清除棋盤

enum color { 
    EMPTY, 
    BLACK, 
    WHITE, 
}; 

struct go_board { 
    unsigned int size; 
    enum color intersections[]; 
};

當enum color player移動時，下面的過程適用：（參見rules）

我正在尋找一種快速（在計算複雜性和實際速度方面）算法來清除板子。你可以幫我嗎？

2013-02-12 fuz

已經測量你的「慢」的方法，並確定它是在應用程序中的瓶頸？首先：使其正確工作;不要擔心表演。 – pmg 2013-02-12 11:03:35

@pmg我想到的「慢」的方法非常不好，我還沒有測試過。計算複雜度爲O（n4），其中n是板的大小。 – fuz 2013-02-12 11:05:03

19^4是*僅* 130321 – pmg 2013-02-12 11:06:33

使用圖像處理的填充算法。首先，用空點填充所有白色或空白的位置;所有未填充白石的位置都將死亡。用黑色重複。

2013-02-12 11:08:57 thiton

這似乎是一個O（n²）算法，看起來相當不錯。我會看看這個。謝謝！ – fuz 2013-02-12 11:10:30

這可以工作，但我不得不承認我不知道我明白。它可能行不通：在Go中，有些羣體無條件地活着（2個或更多的眼睛，或者相互連接的羣體之間有幾個假眼睛），還有一些羣體是「相互依存」的（seki，...）。我不確定這可以簡單地回到一個簡單的填充算法。 – 2013-02-13 09:32:46

@Olivier我只問一些因爲他們沒有自由而被刪除的團體。我的用例中不需要更多計算。 – fuz 2013-03-13 17:40:41

您可以保留對電路板上每個組的參考，並跟蹤他們的自由。對於每個添加的寶石，您最多隻需合併/更新4個組。是我還是這聽起來像O（K）？:)

（編輯）

2014-03-27 11:04:01 okw

這對我有什麼幫助？ Go板不完全稀疏。 – fuz 2014-03-27 20:10:42

的確，我回答得太快orz讓我編輯我的答案。 – okw 2014-03-28 04:54:12

回答