827. Making A Large Island
Đề Bài
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Example 1:
Input: grid = [[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: grid = [[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: grid = [[1,1],[1,1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4.
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j]is either0or1.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(V+E)
💾 Không gian
O(V)
Lời Giải
C++
0827-making-a-large-island.cpp
class Solution {
private:
vector<vector<int>> components, grid;
unordered_map<int, int> sizes;
int n;
public:
const int di[4] = {-1, 1, 0, 0};
const int dj[4] = {0, 0, -1, 1};
bool isValid(int i, int j) {
return 0 <= i and i < n and 0 <= j and j < n;
}
int dfs(int i, int j, int color) {
if (!isValid(i, j)) {
return 0;
}
if (!(grid[i][j] == 1 and components[i][j] == -1)) {
return 0;
}
components[i][j] = color;
int cnt = 1;
for (int p = 0; p < 4; ++p) {
cnt += dfs(i + di[p], j + dj[p], color);
}
return cnt;
}
int largestIsland(vector<vector<int>>& grid) {
this->grid = grid;
n = grid.size();
components.resize(n, vector<int>(n, -1));
int color = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] and components[i][j] == -1) {
sizes[color] = dfs(i, j, color);
color++;
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (!grid[i][j]) {
unordered_set<int> setColor;
for (int p = 0; p < 4; ++p) {
int ni = i + di[p];
int nj = j + dj[p];
if (!isValid(ni, nj)) {
continue;
}
if (grid[ni][nj]) {
setColor.insert(components[ni][nj]);
}
}
int totalSize = 0;
for (int color : setColor) {
totalSize += sizes[color];
}
ans = max(ans, totalSize + 1);
}
}
}
return ans == 0 ? n*n : ans;
}
};
Python
0827-making-a-large-island.py
class Solution:
def __init__(self):
self.components = [[]]
self.size = dict()
self.n = 0
self.DIR = [1, 0, -1, 0, 1]
self.grid = [[]]
def isValid(self, r: int, c: int) -> bool:
return 0 <= r < self.n and 0 <= c < self.n
def dfs(self, r: int, c: int, flag: int) -> None:
self.components[r][c] = flag
self.size[flag] += 1
for d in range(4):
nr = r + self.DIR[d]
nc = c + self.DIR[d + 1]
if self.isValid(nr, nc) and self.grid[nr][nc] and self.components[nr][nc] == -1:
self.dfs(nr, nc, flag)
def largestIsland(self, grid: List[List[int]]) -> int:
self.n = len(grid)
self.grid = grid
self.components = [[-1 for _ in range(self.n)] for _ in range(self.n)]
flag = 0
for r in range(self.n):
for c in range(self.n):
if self.grid[r][c] and self.components[r][c] == -1:
self.size[flag] = 0
self.dfs(r, c, flag)
flag += 1
ans = 0
for r in range(self.n):
for c in range(self.n):
if not self.grid[r][c]:
save = set()
for d in range(4):
nr = r + self.DIR[d]
nc = c + self.DIR[d + 1]
if self.isValid(nr, nc) and self.grid[nr][nc] == 1:
save.add(self.components[nr][nc])
total = 1
for flag in save:
total += self.size[flag]
ans = max(ans, total)
return self.n * self.n if not ans else ans