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.
1#include <vector>
2#include <queue>
3#include <cstring>
4
5using namespace std;
6
7class Solution {
8 vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
9 vector<vector<int>> grid;
10 int r, c;
11
12 bool valid(int x, int y) {
13 return x >= 0 && x < r && y >= 0 && y < c && grid[x][y] == 0;
14 }
15
16 bool dfs(int x, int y) {
17 if (x == r - 1) return true;
18 grid[x][y] = 1;
19 for (auto d : directions) {
20 int nx = x + d.first, ny = y + d.second;
21 if (valid(nx, ny) && dfs(nx, ny)) return true;
22 }
23 return false;
24 }
25
26 bool canCross(int day, vector<vector<int>>& cells) {
27 grid = vector<vector<int>>(r, vector<int>(c, 0));
28 for (int i = 0; i <= day; ++i) grid[cells[i][0] - 1][cells[i][1] - 1] = 1;
29 for (int i = 0; i < c; ++i)
30 if (grid[0][i] == 0 && dfs(0, i)) return true;
31 return false;
32 }
33
34public:
35 int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
36 r = row, c = col;
37 int left = 0, right = cells.size() - 1, last = 0;
38 while (left <= right) {
39 int mid = left + (right - left) / 2;
40 if (canCross(mid, cells)) {
41 last = mid;
42 left = mid + 1;
43 } else {
44 right = mid - 1;
45 }
46 }
47 return last + 1;
48 }
49};In this C++ implementation, binary search is coupled with DFS to check for the last passable day. Each day, up to the midpoint in the binary search, is flooded, and DFS checks if a path still exists.
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.
This Python example leverages a union-find data structure to track connectivity across floodable days, marking the last possible cross day once the virtual nodes disconnect.