class Solution:
def minDays(self, grid: List[List[int]]) -> int:
def count_islands():
visited = [[False] * len(grid[0]) for _ in range(len(grid))]
def dfs(x, y):
stack = [(x, y)]
visited[x][y] = True
while stack:
i, j = stack.pop()
for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
ni, nj = i+dx, j+dy
if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and not visited[ni][nj] and grid[ni][nj]:
visited[ni][nj] = True
stack.append((ni, nj))
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] and not visited[i][j]:
dfs(i, j)
count += 1
return count
if count_islands() != 1:
return 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]:
grid[i][j] = 0
if count_islands() != 1:
grid[i][j] = 1
return 1
grid[i][j] = 1
return 2
class Solution {
public:
int minDays(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
auto count_islands = [&]() {
vector<vector<bool>> vis(m, vector<bool>(n, false));
int count = 0;
function<void(int,int)> dfs = [&](int x, int y) {
vis[x][y] = true;
vector<pair<int,int>> dirs{{0,1},{1,0},{-1,0},{0,-1}};
for (auto [dx, dy]: dirs) {
int nx = x+dx, ny = y+dy;
if (nx>=0 && nx<m && ny>=0 && ny<n && !vis[nx][ny] && grid[nx][ny])
dfs(nx, ny);
}
};
for (int i=0; i<m; ++i)
for (int j=0; j<n; ++j)
if (grid[i][j] && !vis[i][j]) {
dfs(i, j);
++count;
}
return count;
};
if (count_islands() != 1) return 0;
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
if (grid[i][j]) {
grid[i][j] = 0;
if (count_islands() != 1) {
grid[i][j] = 1;
return 1;
}
grid[i][j] = 1;
}
}
}
return 2;
}
};
class Solution {
public int minDays(int[][] grid) {
int m = grid.length, n = grid[0].length;
int countIslands() {
boolean[][] visited = new boolean[m][n];
int count = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1 && !visited[i][j]) {
dfs(i, j, visited, grid);
count++;
}
}
}
return count;
}
void dfs(int x, int y, boolean[][] visited, int[][] grid) {
visited[x][y] = true;
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
for (int d = 0; d < 4; d++) {
int nx = x + dx[d], ny = y + dy[d];
if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length && !visited[nx][ny] && grid[nx][ny] == 1) {
dfs(nx, ny, visited, grid);
}
}
}
if (countIslands() != 1) return 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
grid[i][j] = 0;
if (countIslands() != 1) {
grid[i][j] = 1;
return 1;
}
grid[i][j] = 1;
}
}
}
return 2;
}
}
var minDays = function(grid) {
const m = grid.length, n = grid[0].length;
function countIslands() {
const visited = Array.from({length: m}, () => Array(n).fill(false));
let count = 0;
function dfs(x, y) {
visited[x][y] = true;
for (const [dx, dy] of [[0,1],[1,0],[-1,0],[0,-1]]) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] === 1) {
dfs(nx, ny);
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1 && !visited[i][j]) {
dfs(i, j);
count++;
}
}
}
return count;
}
if (countIslands() !== 1) return 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
grid[i][j] = 0;
if (countIslands() !== 1) {
grid[i][j] = 1;
return 1;
}
grid[i][j] = 1;
}
}
}
return 2;
};
You are given a 2D grid of size m x n consisting of only 0s (water) and 1s (land). An island is a group of 1s connected 4-directionally (up, down, left, right).
Your task is to return the minimum number of days needed to disconnect the island.
In one day, you can change any single land cell (1) into a water cell (0).
The island is considered disconnected if there is no island (all water), or there is more than one island (the land splits into multiple groups).
0 if the grid is already disconnected.1 if disconnecting the island is possible by changing one land cell.2.Key constraints:
The core of the problem is to determine how many land cells need to be removed (turned into water) so that the original island becomes disconnected. At first glance, a brute-force approach would be to try removing each land cell one by one, checking after each removal if the island is disconnected. If not, try removing two cells, and so on.
However, this approach can be very inefficient, especially for larger grids. Instead, we can optimize by first checking if the grid is already disconnected (zero or multiple islands). If not, then for each land cell, try removing it and check if this action disconnects the island. If none of the single removals work, we know that at most two removals are needed due to the problem's constraints (the grid is small, and this is a property of 2D connectivity).
The key insight is that, except for rare cases (like a single land cell or a "bridge" cell), disconnecting the island usually requires removing one or two cells at most. This allows us to avoid checking all combinations of two or more cells, making the solution efficient.
0 immediately.1), temporarily change it to water (0), then count the number of islands again.
1.2 (since with at most two removals, the island can always be disconnected in a 2D grid).Why use DFS/BFS? DFS or BFS is used to efficiently traverse all connected land cells and count the number of distinct islands. By marking visited cells, we avoid revisiting the same land cell multiple times, ensuring O(m*n) time for each count.
Why not check all pairs for two removals? The problem guarantees that if one removal does not disconnect the island, then two removals will always suffice, so we do not need to check all pairs, which would be too slow.
Example Input:
grid = [
[1,1],
[1,1]
]
2.
Another Example:
grid = [
[1,0],
[1,1]
]
Remove (1,0): grid becomes [[1,0],[0,1]]. Now, there are two islands. So, return 1.
The problem asks how quickly we can disconnect an island by removing land cells. By leveraging DFS/BFS to count islands and trying single-cell removals, we efficiently determine whether 0, 1, or 2 days are needed. The elegant insight is that in a small 2D grid, two removals always suffice if one does not, so no need to brute-force all combinations. This approach is both clean and optimal for the constraints.