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.
1function minDays(grid) {
2 const directions = [[0,1],[1,0],[0,-1],[-1,0]];
3 function disconnected() {
4 const visited = new Array(grid.length).fill().map(() => new Array(grid[0].length).fill(false));
5 let islands = 0;
6
7 function dfs(r, c) {
8 const stack = [[r, c]];
9 while (stack.length) {
10 const [x, y] = stack.pop();
11 if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || visited[x][y] || grid[x][y] === 0) continue;
12 visited[x][y] = true;
13 for (const [dx, dy] of directions) stack.push([x + dx, y + dy]);
14 }
15 }
16
17 for (let r = 0; r < grid.length; r++) {
18 for (let c = 0; c < grid[0].length; c++) {
19 if (grid[r][c] === 1 && !visited[r][c]) {
20 dfs(r, c);
21 islands++;
22 }
23 }
24 }
25 return islands !== 1;
26 }
27
28 if (disconnected()) return 0;
29
30 for (let r = 0; r < grid.length; r++) {
31 for (let c = 0; c < grid[0].length; c++) {
32 if (grid[r][c] === 1) {
33 grid[r][c] = 0;
34 if (disconnected()) return 1;
35 grid[r][c] = 1;
36 }
37 }
38 }
39
40 return 2;
41}This JavaScript solution also uses DFS to ascertain if the grid is disconnected. It checks all coordinates initially for disconnection and tests each 1 by setting it to 0 and checking disconnection status. The logic parallels the Python solution in structure and approach.
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.