| 日期 |
2022年9月18日 |
| 是否独立完成 |
是 |
| 涉及算法 |
广度优先搜索、哈希表 |
题面
LeetCode 827. 最大人工岛
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
示例 1：
1
2
3
| 输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
|
示例 2：
1
2
3
| 输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。
|
示例 3：
1
2
3
| 输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。
|
题解
广度优先搜索+哈希表
可以用广度优先搜索把每个岛都标记成对应的下标（为了方便后续统计总面积，将下标定为由-1开始增长的负整数），每搜索完一个岛就把其对应的面积存在哈希表里。然后第开始第二次遍历，遇到0就计算其周围四格的岛的面积，并实时更新最大值。
代码：
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
| class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
int n = grid.size();
unordered_map<int, int> area;
int idx = -1;
vector<int> dir{ -1,0,1,0,-1 };
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) continue;
queue<pair<int, int>> q;
q.push({ i,j });
int cnt = 0;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
int r = cur.first, c = cur.second;
if (grid[r][c] < 0) continue;
grid[r][c] = idx;
for (int d = 0; d < 4; d++) {
int nr = r + dir[d], nc = c + dir[d + 1];
if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] <= 0) continue;
q.push({ nr,nc });
}
cnt++;
}
area[idx] = cnt;
idx--;
}
}
int res = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) continue;
unordered_set<int> visited;
for (int d = 0; d < 4; d++) {
int ni = i + dir[d], nj = j + dir[d + 1];
if (ni < 0 || ni >= n || nj < 0 || nj >= n || grid[ni][nj] >= 0 || visited.count(grid[ni][nj])) continue;
visited.insert(grid[ni][nj]);
grid[i][j] += area[grid[ni][nj]];
}
res = max(res, grid[i][j]);
}
}
if (res == -1) return area[-1];
else return res + 1;
}
};
|