class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
}
};
827. 最大人工岛
给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 形成。
示例 1:
输入: grid = [[1, 0], [0, 1]] 输出: 3 解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
示例 2:
输入: grid = [[1, 1], [1, 0]] 输出: 4 解释: 将一格0变成1，岛屿的面积扩大为 4。
示例 3:
输入: grid = [[1, 1], [1, 1]] 输出: 4 解释: 没有0可以让我们变成1，面积依然为 4。
提示：
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j] 为 0 或 1原站题解
golang 解法, 执行用时: 240 ms, 内存消耗: 14.1 MB, 提交时间: 2023-09-28 14:52:33
func largestIsland(grid [][]int) (ans int) {
dir4 := []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
n, t := len(grid), 0
tag := make([][]int, n)
for i := range tag {
tag[i] = make([]int, n)
}
area := map[int]int{}
var dfs func(int, int)
dfs = func(i, j int) {
tag[i][j] = t
area[t]++
for _, d := range dir4 {
x, y := i+d.x, j+d.y
if 0 <= x && x < n && 0 <= y && y < n && grid[x][y] > 0 && tag[x][y] == 0 {
dfs(x, y)
}
}
}
for i, row := range grid {
for j, x := range row {
if x > 0 && tag[i][j] == 0 { // 枚举没有访问过的陆地
t = i*n + j + 1
dfs(i, j)
ans = max(ans, area[t])
}
}
}
for i, row := range grid {
for j, x := range row {
if x == 0 { // 枚举可以添加陆地的位置
newArea := 1
conn := map[int]bool{0: true}
for _, d := range dir4 {
x, y := i+d.x, j+d.y
if 0 <= x && x < n && 0 <= y && y < n && !conn[tag[x][y]] {
newArea += area[tag[x][y]]
conn[tag[x][y]] = true
}
}
ans = max(ans, newArea)
}
}
}
return
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
javascript 解法, 执行用时: 216 ms, 内存消耗: 65 MB, 提交时间: 2023-09-28 14:52:19
/**
* @param {number[][]} grid
* @return {number}
*/
const d = [0, -1, 0, 1, 0];
var largestIsland = function(grid) {
let n = grid.length, res = 0;
const tag = new Array(n).fill(0).map(() => new Array(n).fill(0));
const area = new Map();
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1 && tag[i][j] === 0) {
const t = i * n + j + 1;
area.set(t, dfs(grid, i, j, tag, t));
res = Math.max(res, area.get(t));
}
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 0) {
let z = 1;
const connected = new Set();
for (let k = 0; k < 4; k++) {
let x = i + d[k], y = j + d[k + 1];
if (!valid(n, x, y) || tag[x][y] == 0 || connected.has(tag[x][y])) {
continue;
}
z += area.get(tag[x][y]);
connected.add(tag[x][y]);
}
res = Math.max(res, z);
}
}
}
return res;
}
const dfs = (grid, x, y, tag, t) => {
let n = grid.length, res = 1;
tag[x][y] = t;
for (let i = 0; i < 4; i++) {
let 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;
}
const valid = (n, x, y) => {
return x >= 0 && x < n && y >= 0 && y < n;
};
java 解法, 执行用时: 80 ms, 内存消耗: 72.5 MB, 提交时间: 2023-09-28 14:52:02
class Solution {
static int[] d = {0, -1, 0, 1, 0};
public int largestIsland(int[][] grid) {
int n = grid.length, res = 0;
int[][] tag = new int[n][n];
Map<Integer, Integer> area = new HashMap<Integer, Integer>();
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.put(t, dfs(grid, i, j, tag, t));
res = Math.max(res, area.get(t));
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 0) {
int z = 1;
Set<Integer> connected = new HashSet<Integer>();
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.contains(tag[x][y])) {
continue;
}
z += area.get(tag[x][y]);
connected.add(tag[x][y]);
}
res = Math.max(res, z);
}
}
}
return res;
}
public int dfs(int[][] grid, int x, int y, int[][] tag, int t) {
int n = grid.length, 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;
}
public boolean valid(int n, int x, int y) {
return x >= 0 && x < n && y >= 0 && y < n;
}
}
cpp 解法, 执行用时: 540 ms, 内存消耗: 151.5 MB, 提交时间: 2023-09-28 14:51:48
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;
}
};
python3 解法, 执行用时: 1368 ms, 内存消耗: 37.2 MB, 提交时间: 2023-09-28 14:51:28
'''
我们给每个岛屿进行标记，标记值与岛屿的某个 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 加上该点所在的岛屿面积，并且将该岛屿加入集合中。
所有这些新合并岛屿以及原来的岛屿的面积的最大值就是最大的岛屿面积。
'''
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
tag = [[0] * n for _ in range(n)]
area = Counter()
# dfs(i, j) 与grid[i][j] 相连的岛屿面积
def dfs(i: int, j: int) -> None:
tag[i][j] = t
area[t] += 1
for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): # 四个方向搜索未搜索过的岛屿
if 0 <= x < n and 0 <= y < n and grid[x][y] == 1 and tag[x][y] == 0:
dfs(x, y)
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x and tag[i][j] == 0: # 枚举没有访问过的陆地
t = i * n + j + 1
dfs(i, j)
ans = max(area.values(), default=0)
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 0: # 枚举可以添加陆地的位置
new_area = 1
connected = {0}
for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): # 四个方向
if 0 <= x < n and 0 <= y < n and tag[x][y] not in connected:
new_area += area[tag[x][y]]
connected.add(tag[x][y])
ans = max(ans, new_area)
return ans