leetcode 695. 岛屿的最大面积

题目如下

数据范围

示例

这道题可以直接用搜索来找最大面积 但是博主想回忆一下并查集的写法所以用了并查集。

通过代码

class bin{
    public:
    vector<int> g,v;
    int max1 = 0;
    bin(vector<vector<int>>& t,int n,int m){
        g = vector<int>(n * m,0);
        v = vector<int>(n * m,0);
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(t[i][j] == 1){
                    max1 = 1;
                    g[(i * m) + j] = (i * m) + j;
                    v[(i * m) + j] = 1;
                }
            }
        }
        
     
    }
    int find(int a){
        if(a == g[a])return a;
        g[a] = find(g[a]);
        return g[a];
    }
    void un(int a,int b){
        int fb = find(b);
        int fa = find(a);
        if(fb == fa)return;
        g[fb] = fa;
        v[fa] += v[fb];
        max1 = max(max1,v[fa]);
        
    }
};
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        bin b(grid,n,m);
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(grid[i][j] == 1){
                    
                    if(j > 0 && grid[i][j - 1] == 1){
                        b.un((i * m) + j,(i * m) + j - 1);
                    }
                    if(i > 0 && grid[i - 1][j] == 1){
                        b.un((i * m) + j,((i - 1) * m) + j);
                    }
                }
            }
        }
        return b.max1;
      
    }
};

这里补上搜索代码

class Solution {
public:
    int max1 = 0;
    void dfs(vector<vector<int>>& g, int x, int y) {
        if (x < 0 || x >= g.size() || y < 0 || y >= g[0].size() ||
            g[x][y] == 0)
            return;
        g[x][y] = 0;//有些时候可以把已经遍历的地方置为0可以节约访问数组空间
        max1 += 1;
        dfs(g, x - 1, y);
        dfs(g, x, y - 1);
        dfs(g, x + 1, y);
        dfs(g, x, y + 1);
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    max1 = 0;
                    dfs(grid, i, j) ;
                    ans = max(ans, max1);
                }
            }
        }
        return ans;
    }
};