Sponsored
Sponsored
This approach employs a breadth-first search (BFS) to explore the grid, counting the number of islands. Initially, it checks if the grid is already disconnected. If not, it attempts to disconnect the grid by changing each land cell to water one-by-one, checking the number of islands created each time. If the transformation disconnects the grid, the process stops early. This approach is based on the premise that if converting any one land cell to water does not suffice, converting two will.
Time Complexity: O((m*n)^2), where m and n are grid dimensions due to the nested loop and re-evaluation of the grid connect status for each cell transformation.
Space Complexity: O(m*n) for the BFS queue and visited marker.
1def minDays(grid):
2 def connected():
3 seen = set()
4 def dfs(r, c):
5 if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]) or grid[r][c] == 0 or (r, c) in seen:
6 return 0
7 seen.add((r, c))
8 for x, y in ((r, c+1), (r+1, c), (r, c-1), (r-1, c)):
9 dfs(x, y)
10 return 1
11 cnt = sum(dfs(r, c) for r in range(len(grid)) for c in range(len(grid[0])))
12 return cnt != 1
13
14 if connected():
15 return 0
16
17 rows, cols = len(grid), len(grid[0])
18 for r in range(rows):
19 for c in range(cols):
20 if grid[r][c] == 1:
21 grid[r][c] = 0
22 if connected():
23 return 1
24 grid[r][c] = 1
25
26 return 2The function connected() uses BFS to count the number of islands. Initially, if the grid is already disconnected (more than one island), it returns 0. Otherwise, it tries flipping each 1 to 0 and checks again if the grid becomes disconnected. If so, it returns 1. If no single flip works, it's guaranteed disconnect happens after flipping two cells, hence returning 2.
This approach utilizes a union-find (disjoint set union, DSU) data structure to efficiently manage and check connected components within the grid. Initially, it checks the number of islands using the union-find approach. Then, it assesses the effect of converting each land cell to water, employing union-find to determine if it results in a disconnected structure.
Time Complexity: O((m*n))
Space Complexity: O(m*n)
1#include <vector>
2#include <numeric>
3using namespace std;
4
5class UnionFind {
vector<int> parent, rank;
public:
UnionFind(int n) : parent(n), rank(n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int u) {
if (u != parent[u]) {
parent[u] = find(parent[u]);
}
return parent[u];
}
bool unite(int u, int v) {
int rootU = find(u), rootV = find(v);
if (rootU != rootV) {
if (rank[rootU] > rank[rootV]) parent[rootV] = rootU;
else if (rank[rootU] < rank[rootV]) parent[rootU] = rootV;
else { parent[rootV] = rootU; rank[rootU]++; }
return true;
}
return false;
}
};
int minDays(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
auto withinGrid = [&](int i, int j) { return i >= 0 && j >= 0 && i < m && j < n; };
int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
function<bool()> isConnected = [&]() {
UnionFind uf(m * n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
for (auto &dir : directions) {
int ni = i + dir[0], nj = j + dir[1];
if (withinGrid(ni, nj) && grid[ni][nj] == 1) {
uf.unite(i*n + j, ni*n + nj);
}
}
}
}
}
int islandCount = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1 && uf.find(i*n + j) == i*n + j) {
islandCount++;
if (islandCount > 1) return false;
}
}
}
return islandCount == 1;
};
if (!isConnected()) 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 (!isConnected()) return 1;
grid[i][j] = 1;
}
}
}
return 2;
}The program starts by implementing a union-find class to handle connected components effectively. The isConnected function sets up the union-find structure, uniting land cells that are connected. Through union-find's efficiency, we can quickly assess if the grid is disconnected. If the initial grid has multiple islands, it returns 0. The function evaluates single cell changes using union-find as a checker for grid disconnection, ensuring optimized performance.