In a 2D grid of 0s and 1s, we change at most one 0 to a 1.
After, what is the size of the largest island? (An island is a 4-directionally connected group of 1s).
Example 1:
Input: [[1, 0], [0, 1]] Output: 3 Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example 2:
Input: [[1, 1], [1, 0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example 3:
Input: [[1, 1], [1, 1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4.
Notes:
1 <= grid.length = grid[0].length <= 50.0 <= grid[i][j] <= 1.
Related Topics:
Depth-first Search
// OJ: https://leetcode.com/problems/making-a-large-island/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class UnionFind {
vector<int> id, size;
public:
UnionFind(int N) : id(N), size(N, 1) {
iota(begin(id), end(id), 0);
}
int find(int x) {
return id[x] == x ? x : (id[x] = find(id[x]));
}
void connect(int x, int y) {
int p = find(x), q = find(y);
if (p == q) return;
id[p] = q;
size[q] += size[p];
}
int getSize(int x) { return size[find(x)]; }
};
class Solution {
public:
int largestIsland(vector<vector<int>>& G) {
int M = G.size(), N = G[0].size(), dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}, ans = 0;
UnionFind uf(M * N);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (G[i][j] == 0) continue;
for (auto &[dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == 0) continue;
uf.connect(i * N + j, x * N + y);
}
ans = max(ans, uf.getSize(i * N + j));
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (G[i][j] == 1) continue;
unordered_map<int, int> m;
for (auto &[dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (x < 0 || y < 0 || x >= M || y >= N || G[x][y] == 0) continue;
m[uf.find(x * N + y)] = uf.getSize(x * N + y);
}
int size = 1;
for (auto &p : m) size += p.second;
ans = max(ans, size);
}
}
return ans;
}
};