计算机科学基础leetcode刷题图
Source
Edit
History

最大人工岛

Problem: 827. 最大人工岛

Reference

代码随想录 (programmercarl.com)

思路

先深度优先搜索,为每一片岛屿编号,并且记录岛屿的面积,用map做映射,方便后面遍历海洋能够得到他四周的岛屿的面积。

遍历海洋块,得到海洋快四周的岛屿的面积,将海洋快四周的岛屿的面积相加,得到当前海洋快变成路地块所得的总面积。

再取最大值。

需要注意: 得到海洋快四周的岛屿的面积,时不要重复添加,标记海洋快添加过的岛屿,并且不再添加。

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
public:
    int cnt = 0;
    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visted, int x,
             int y, int mark) {
        if (visted[x][y])
            return;
        cnt++;
        visted[x][y] = true;
        grid[x][y] = mark;
        pair<int, int> neigbors[4]{
            pair<int, int>(x, y + 1), pair<int, int>(x + 1, y),
            pair<int, int>(x, y - 1), pair<int, int>(x - 1, y)};
        for (pair<int, int> neigbor : neigbors) {
            if (neigbor.first >= grid.size() ||
                neigbor.second >= grid[0].size() || neigbor.first < 0 ||
                neigbor.second < 0) // 越界
                continue;
            if (grid[neigbor.first][neigbor.second] == 0) // 海洋
                continue;
            if (visted[neigbor.first][neigbor.second]) // 访问过了
                continue;
            dfs(grid, visted, neigbor.first, neigbor.second, mark);
        }
    }

    int largestIsland(vector<vector<int>>& grid) {
        unordered_map<int, int> islandsGridNum;
        int mark = 2;
        bool allIsland = true;
        vector<vector<bool>> visted(grid.size(),vector<bool>(grid[0].size(), false));
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if(grid[i][j] == 0) allIsland = false;
                if (!visted[i][j] && grid[i][j] == 1) {
                    cnt = 0;
                    dfs(grid, visted, i, j, mark);
                    islandsGridNum[mark] = cnt;
                    mark++;
                }
            }
        }

        // for (pair<int, int> item : islandsGridNum) {
        //     cout << item.first << "--" << item.second << endl;
        // }

        // 全是陆地返回面积
        if (allIsland) return grid.size() * grid[0].size();

        int res = 0;
        unordered_set<int> vistedIsland;
        // 遍历海洋得到附近的岛屿
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                int sum = 1;
                vistedIsland.clear();
                if (grid[i][j] == 0) {
                    pair<int, int> neigbors[4]{
                        pair<int, int>(i, j + 1), pair<int, int>(i + 1, j),
                        pair<int, int>(i, j - 1), pair<int, int>(i - 1, j)};
                    for (pair<int, int> neigbor : neigbors) {
                        if (neigbor.first >= grid.size() ||
                            neigbor.second >= grid[0].size() ||
                            neigbor.first < 0 || neigbor.second < 0) // 越界
                            continue;
                        if (grid[neigbor.first][neigbor.second] == 0) // 海洋
                            continue;
                        if (vistedIsland.find(
                                grid[neigbor.first][neigbor.second]) !=
                            vistedIsland.end()) // 添加过该岛屿了
                            continue;
                        vistedIsland.insert(
                            grid[neigbor.first][neigbor.second]);
                        // cout << "岛屿编号" << grid[neigbor.first][neigbor.second]
                        //      << "岛屿大小" << islandsGridNum[grid[neigbor.first][neigbor.second]] << endl;
                        sum += islandsGridNum[grid[neigbor.first][neigbor.second]];
                    }
                }
                res = max(sum, res);
            }
        }
        return res;
    }
};