力扣827. 最大人工岛

力扣827. 最大人工岛

题目

题目解析及思路

题目要求在最多将1个0变成1的前提下得到的最大连通块面积

暴力想法是枚举每一个0变成1，然后搜索求面积

实际上在操作过程中，每一块原来的岛屿我们都重复计算了，因此不妨先整体dfs把每个岛屿标上号，并记录面积

在枚举0的时候遍历它的上下左右把相邻的岛屿编号记录(需要去重)，然后求和

代码

class Solution {
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        //记录每个岛屿面积
        vector<int> area;
        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            grid[i][j] = area.size() + 2;
            int size = 1;
            for(auto& [dx,dy] : dirs){
                int x = i + dx,y = j + dy;
                if (0 <= x && x < n && 0 <= y && y < n && grid[x][y] == 1){
                    size += dfs(x,y);
                }
            }
            return size;
        };

        //整体dfs
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j] == 1){
                    area.push_back(dfs(i,j));
                }
            }
        }

        if(area.empty()){
            return 1;
        }

        int res = 0;
        //记录相邻的岛屿编号
        unordered_set<int> s;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]) continue;
                s.clear();
                int new_area = 1;
                for(auto& [dx,dy]:dirs){
                    int x = i + dx,y = j + dy;
                    //之前没有计算过的才计算
                    if (0 <= x && x < n && 0 <= y && y < n && grid[x][y] && s.find(grid[x][y]) == s.end()){
                        new_area += area[grid[x][y] - 2];
                        s.insert(grid[x][y]);
                    }
                }
                res = max(res,new_area);
            }
        }
        return res?res:n*n;
    }
};