連鄰居二維數組

Question

我設計的引擎的遊戲，其中有一個二維數組，像這樣：

0,1,1,2,0 
0,1,2,1,1 
1,0,1,0,2 
2,1,2,0,0 
2,0,1,0,0 

我卡在「遊戲結束」的條件，因爲它必須檢查如果1或2被連接。 它應與1點的申報玩家爲獲勝者，並返回此：

1 1 
1 1 1 
1 1 
1 
    1 
    1 

我使用遞歸通過檢查陣列中的每個位置，並檢查其鄰國在所有8個方向，但嘗試過的方法花了45秒運行這是低效的。

有沒有人有任何想法？一個僞代碼的例子將不勝感激（我是一個緩慢的學習者）。

Answer 1

繼續前進，使一個副本圖形a[n][n]與a[i][j] = 1如果i和j連接的算法。

然後你就可以做到以下幾點：

int count = 0; 

void dfs(int i) 
{ 
    int k; 
    for(k = 0; k < n; k++) 
    { 
     if(A[i][k] == 1 && !visited[k]) 
     { 
      count++; 
      visited[k] = 1; 
      dfs(k); 
     } 
    } 
} 

for(i=0; i < n;i++) 
{ 
    if(!visited[i]) 
    { 
     count=1; 
     visited[i]=1; 
     dfs(i); 
     // map i with count .. here 
    } 
} 

所以一旦你這樣做，其節點的一個映射節點的計數的網絡。

你會發現數值計數，如果計數== total_no_of_1的

如果是這樣那麼網絡1連接。如果沒有，那麼有2個相同的和並宣佈結果。

Answer 2

這裏有一些提示：

• 如果可能的話，跟蹤1和2有多少的還有從一開始。
• 當檢查它們是否連接時，可以使用boolean矩陣和一個計數器來跟蹤哪些已經檢查過，以及它們有多少個。
• 在必要的鄰居上使用遞歸而不是檢查矩陣中的每個位置。

Answer 3

這個問題並不那麼容易。在我看來，您可以將您的矩陣看作一個圖表，然後嘗試查看您的圖表是否已連接。即是連接的1s的曲線圖，並且是連接的2s的曲線圖。在這裏你看到一個few algorithms。由於您正在創建圖形，您還可以跟蹤播放器正在創建的節點組，並且在創建新節點時，可以檢查新節點連接的新節點數量和聯合節點數量（或如果它沒有連接任何東西，創建一個包含新節點的新組）。

btw您可以將任何遞歸轉換爲循環，但只有當您的堆棧耗盡時才需要這樣做。

Answer 4

從頭開始維護一個UnionFind數據結構，每個條目代表每個單元格。最初，在具有相同值的相鄰單元上執行聯合。當玩家標記一個單元格時，如果該值與玩家的值相同，則執行與相鄰單元格的聯合（）。在聯盟查找中，您可以跟蹤具有某個值的單元格數量，當該數字等於該值的插入次數時，您就有贏家。

你這樣做，也是使用線性描述here

Answer 5

你需要的是：

Connected_component_labeling

這給出了一個僞代碼，

希望它有助於