【827. 最大人工岛】

来源：力扣（LeetCode）

描述：

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
1
2
3

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
1
2
3

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
1
2
3

提示：

• n == grid.length

• n == grid[i].length

• 1 <= n <= 500

• grid[i][j] 为 0 或 1

方法：标记岛屿 + 合并

  我们给每个岛屿进行标记，标记值与岛屿的某个 grid[i][j] 有关，即 t = i × n + j + 1，t 唯一。使用 tag 记录每个点所属的岛屿的标记，并且使用哈希表 area 保存每个岛屿的面积。岛屿的面积可以使用深度优先搜索或广度优先搜索计算。

  对于每个 grid[i][j] = 0，我们计算将它变为 1 后，新合并的岛屿的面积 z（z 的初始值为 1，对应该点的面积）：使用集合 connected 保存与 grid[i][j] 相连的岛屿，遍历与 grid[i][j] 相邻的四个点，如果该点的值为 1，且它所在的岛屿并不在集合中，我们将 z 加上该点所在的岛屿面积，并且将该岛屿加入集合中。所有这些新合并岛屿以及原来的岛屿的面积的最大值就是最大的岛屿面积。

代码：

const vector<int> d = {0, -1, 0, 1, 0};

class Solution {
public:
    bool valid(int n, int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }

    int dfs(const vector<vector<int>> &grid, int x, int y, vector<vector<int>> &tag, int t) {
        int n = grid.size(), res = 1;
        tag[x][y] = t;
        for (int i = 0; i < 4; i++) {
            int x1 = x + d[i], y1 = y + d[i + 1];
            if (valid(n, x1, y1) && grid[x1][y1] == 1 && tag[x1][y1] == 0) {
                res += dfs(grid, x1, y1, tag, t);
            }
        }
        return res;
    }

    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size(), res = 0;
        vector<vector<int>> tag(n, vector<int>(n));
        unordered_map<int, int> area;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && tag[i][j] == 0) {
                    int t = i * n + j + 1;
                    area[t] = dfs(grid, i, j, tag, t);
                    res = max(res, area[t]);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    int z = 1;
                    unordered_set<int> connected;
                    for (int k = 0; k < 4; k++) {
                        int x = i + d[k], y = j + d[k + 1];
                        if (!valid(n, x, y) || tag[x][y] == 0 || connected.count(tag[x][y]) > 0) {
                            continue;
                        }
                        z += area[tag[x][y]];
                        connected.insert(tag[x][y]);
                    }
                    res = max(res, z);
                }
            }
        }
        return res;
    }
};
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

执行用时：468 ms, 在所有 C++ 提交中击败了59.83%的用户
内存消耗：151.1 MB, 在所有 C++ 提交中击败了37.29%的用户
复杂度分析
时间复杂度：O(n²)，其中 n 是 grid 的长与宽。使用深度优先搜索获取岛屿面积时，总共访问不超过 n² 个点。
空间复杂度：O(n²)。保存 tag 与 area 需要 O(n²) 的空间。
author：LeetCode-Solution