827. 最大人工岛.cpp

我写的

class Solution {
public:
    int largestIsland(vector<vector<int>> &grid) {

        // 用于广度优先遍历 grid
        queue<vector<int>> q;
        // 记录岛屿的信息
        vector<Island*> islands;

        int maxIsland = 0;
        // 这个用于求岛的面积和岛中有哪些点
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {

                if (grid[i][j] != 1) {
                    continue;
                }

                int sum = 0;
                Island *island = new Island;
                q.push({i, j});
                while (! q.empty()) {
                    int n = q.size();
                    for (int k = 0; k < n; ++k) {
                        sum += 1;

                        int x = q.front()[0];
                        int y = q.front()[1];

                        grid[x][y] = 2;

                        q.pop();
                        // 将点放到 set 集合中, 便于后面的判断
                        island->points.insert({x, y});
                        if (y - 1 >= 0 && grid[x][y - 1] == 1) { q.push({x, y - 1}); grid[x][y-1] = 3; }
                        if (y + 1 < grid.size() && grid[x][y + 1] == 1) {q.push({x, y + 1}); grid[x][y+1] =3; }
                        if (x - 1 >= 0 && grid[x - 1][y] == 1) {q.push({x - 1, y}); grid[x-1][y] = 3;}
                        if (x + 1 < grid[i].size() && grid[x + 1][y] == 1) {q.push({x + 1, y}); grid[x+1][y] = 3;}
                    }
                }

                island->area = sum;
                maxIsland = max(sum, maxIsland);
                islands.push_back(island);
            }
        }

        int res = 0;

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j] != 0) {
                    continue;
                }

                int sum = 0;

                int x = i;
                int y = j;

                set<Island*> choose;

                // 根据当前补的点计算周围点所在的岛屿, 估计就是这个地方速度慢了
                for (auto& island : islands) {
                    if (y - 1 >= 0 && grid[x][y - 1] == 2 && island->points.find({x, y - 1}) != island->points.end() && choose.find(island) == choose.end()) {
                        sum += island->area;
                        choose.insert(island);
                    }

                    if (y + 1 < grid.size() && grid[x][y + 1] == 2 && island->points.find({x, y + 1}) != island->points.end() && choose.find(island) == choose.end()) {
                        sum += island->area;
                        choose.insert(island);
                    }

                    if (x - 1 >= 0 && grid[x - 1][y] == 2 && island->points.find({x-1, y}) != island->points.end() && choose.find(island) == choose.end()) {
                        sum += island->area;
                        choose.insert(island);
                    }

                    if (x + 1 < grid[i].size() && grid[x + 1][y] == 2 && island->points.find({x+1, y}) != island->points.end() && choose.find(island) == choose.end()) {
                        sum += island->area;
                        choose.insert(island);
                    }
                }

                sum += 1;

                res = max(sum, res);
            }
        }

        return max(maxIsland, res);
    }
};

本文来自：https://blog.duhbb.com

本文链接地址：827. 最大人工岛.cpp，英雄不问来路，转载请注明出处，谢谢。

有话想说：那就赶紧去给我留言吧。