我正在解決LeetCode.com上一個名為 Number of Islands 的問題：
給定一個表示“1”（陸地）和“0”（水）的地圖的 mxn 2D 二進制網格網格，回傳島嶼的數量。島嶼四面環水，由相鄰陸地水平或垂直連接而成。您可以假設網格的所有四個邊緣都被水包圍。
我知道如何用 DFS 解決它，但我正在學習 聯合發現 并提出了以下方法：
class Solution {
public:
vector<int> parent, sz;
int counter;
int find(int i) {
if(parent[i]==i) return i;
return parent[i]=find(parent[i]);
}
void unionf(int one, int two) {
int p1=find(one);
int p2=find(two);
if(p1==p2) return;
if(sz[one]<sz[two]) {
parent[one]=two;
sz[two] =sz[one];
} else {
parent[two]=one;
sz[one] =sz[two];
}
counter--;
}
int numIslands(vector<vector<char>>& grid) {
int m=grid.size(), n=grid[0].size();
parent.resize(m*n);
iota(begin(parent),end(parent),0);
sz.resize(m*n,1);
counter=0;
for(int i=0; i<m; i ) {
for(int j=0; j<n; j ) {
if(grid[i][j]=='0') {
continue;
}
//grid[i][j]=='1'; an island
counter ;
int idx=i*n j;
//traverse all 4 neighbors
if(i 1<m && grid[i 1][j]=='1') unionf(idx,(i 1)*n j);
if(i-1>=0 && grid[i-1][j]=='1') unionf(idx, (i-1)*n j);
if(j 1<n && grid[i][j 1]=='1') unionf(idx, i*n j 1);
if(j-1>=0 && grid[i][j-1]=='1') unionf(idx, i*n j-1);
}
}
return counter;
}
};
它對樣本輸入產生正確的答案，但對[["1","1","1"],["0","1","0"],["1","1","1"]].
在高層次上，我的邏輯是每當我遇到一個島（1）時，我都會增加計數器并呼叫unionf()并嘗試將它與它的鄰居統一起來。如果這樣的統一是可能的，我會減少counter，unionf()因為它鏈接到它的父島（一個連接的組件）而不是一個新島。
有人可以指出我的邏輯中缺少什么嗎？謝謝！
uj5u.com熱心網友回復：
添加一些除錯列印顯示 union: Demo中的一些問題。
更改為：
void unionf(int one, int two) {
int p1=find(one);
int p2=find(two);
if (p1 == p2) return;
if (sz[p1] < sz[p2]) {
parent[p1] = p2;
sz[p2] = sz[p1];
} else {
parent[p2] = p1;
sz[p1] = sz[p2];
}
std::cout << "union:" << one << " and " << two
<< "(p1: " << p1 << ", p2: " << p2 << ")" << std::endl;
counter--;
}
解決問題（雖然不確定島的大小）。
演示
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/410215.html
標籤：