Sponsored
Sponsored
This approach involves using a binary search to find the last day a path exists from top to bottom. For each midpoint in the binary search, simulate the grid's flooding and check path connectivity using Depth First Search (DFS). Start by initializing the grid as land then flood the cells according to the days up to midpoint. Using DFS, attempt to find a path from the top to the bottom row.
Time Complexity is O(n * m * log(n * m)) where n is the number of rows and m is the number of columns. Space Complexity is O(n * m) for the visited matrix.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private int[][] directions = new int[][] {
6 new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0}
7 };
8 private int row, col;
9
10 private bool CanCross(int[][] grid, int r, int c) {
11 var stack = new Stack<(int, int)>();
12 stack.Push((0, c));
13 bool[,] visited = new bool[row, col];
14 visited[0, c] = true;
15 while (stack.Count > 0) {
16 var (x, y) = stack.Pop();
17 if (x == row - 1) return true;
18 foreach (var d in directions) {
19 int nx = x + d[0], ny = y + d[1];
20 if (nx >= 0 && ny >= 0 && nx < row && ny < col && !visited[nx, ny] && grid[nx][ny] == 0) {
21 visited[nx, ny] = true;
22 stack.Push((nx, ny));
23 }
24 }
25 }
26 return false;
27 }
28
29 public int LatestDayToCross(int row, int col, int[][] cells) {
30 this.row = row;
31 this.col = col;
32 int left = 0, right = cells.Length;
33 while (left < right) {
34 int mid = (left + right) / 2;
35 var grid = new int[row][];
36 for (int i = 0; i < row; ++i) grid[i] = new int[col];
37 for (int i = 0; i < mid; ++i) grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
38 bool canCross = false;
39 for (int i = 0; i < col; ++i) {
40 if (grid[0][i] == 0 && CanCross(grid, 0, i)) {
41 canCross = true;
42 break;
43 }
44 }
45 if (canCross) left = mid + 1;
46 else right = mid;
47 }
48 return left;
49 }
50}
This C# representation utilizes binary search in tandem with DFS via stack-based execution to evaluate feasible paths. Paths are checked sequentially up to the midpoint in each binary search iteration.
This approach involves using a union-find data structure to efficiently check connectivity between the top and bottom rows during a binary search over the days. For each day in the binary search, the cells flooded up to that day are processed, and union operations are performed on adjacent land cells. We add virtual top and bottom nodes in the union-find structure to track connectivity between the top and bottom row cells.
Time Complexity is O(n * m * log(n * m)) due to union-find operations, and Space Complexity is O(n * m) for the union-find parent and rank tracking.
public class UnionFind {
private int[] parent;
private int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
public void Union(int x, int y) {
int rootX = Find(x);
int rootY = Find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}
public class Solution {
public int LatestDayToCross(int row, int col, int[][] cells) {
int size = row * col;
var uf = new UnionFind(size + 2);
int top_virtual = size;
int bottom_virtual = size + 1;
for (int left = 0, right = cells.Length; left < right;) {
int mid = left + (right - left) / 2;
var grid = new int[row, col];
Array.Clear(uf.parent, 0, uf.parent.Length);
for (int i = 0; i < uf.parent.Length; ++i) uf.parent[i] = i;
for (int i = 0; i < mid; ++i) {
grid[cells[i][0] - 1, cells[i][1] - 1] = 1;
}
for (int r = 0; r < row; ++r) {
for (int c = 0; c < col; ++c) {
if (grid[r, c] == 0) {
int index = r * col + c;
if (r == 0) {
uf.Union(index, top_virtual);
}
if (r == row - 1) {
uf.Union(index, bottom_virtual);
}
if (r > 0 && grid[r - 1, c] == 0) {
uf.Union((r - 1) * col + c, index);
}
if (c > 0 && grid[r, c - 1] == 0) {
uf.Union(r * col + (c - 1), index);
}
}
}
}
if (uf.Find(top_virtual) == uf.Find(bottom_virtual)) {
left = mid + 1;
} else {
right = mid;
}
}
return left - 1;
}
}
The C# solution is constructed around union-find data structures, simultaneously processing each grid flood condition to determine connectivity and ultimately the latest walkable day through a binary search routine.