0

我正在解决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()因为它链接到它的父岛（一个连接的组件）而不是一个新岛。

有人可以指出我的逻辑中缺少什么吗？谢谢！

4

1 回答 1

0

添加一些调试打印显示 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--;
}

解决问题（虽然不确定岛的大小）。

演示

于 2022-01-12T09:25:37.967 回答