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 <stdio.h>
2#include <string.h>
3#include <stdbool.h>
4
5#define MAX 20000
6
7int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
8bool visited[MAX][MAX];
9
10bool isValid(int x, int y, int row, int col, int matrix[MAX][MAX]) {
11 return (x >= 0 && x < row && y >= 0 && y < col && matrix[x][y] == 0 && !visited[x][y]);
12}
13
14bool dfs(int x, int y, int row, int col, int matrix[MAX][MAX]) {
15 if (x == row - 1) return true;
16 visited[x][y] = true;
17 for (int i = 0; i < 4; i++) {
18 int newX = x + directions[i][0];
19 int newY = y + directions[i][1];
20 if (isValid(newX, newY, row, col, matrix)) {
21 if (dfs(newX, newY, row, col, matrix)) return true;
22 }
23 }
24 return false;
25}
26
27bool canCross(int row, int col, int cells[][2], int day, int matrix[MAX][MAX]) {
28 memset(matrix, 0, sizeof(int) * MAX * MAX);
29 memset(visited, false, sizeof(bool) * MAX * MAX);
30 for (int i = 0; i <= day; i++) {
31 matrix[cells[i][0] - 1][cells[i][1] - 1] = 1;
32 }
33 for (int i = 0; i < col; i++) {
34 if (matrix[0][i] == 0 && dfs(0, i, row, col, matrix)) return true;
35 }
36 return false;
37}
38
39int latestDayToCross(int row, int col, int cells[][2], int cellsSize) {
40 int matrix[MAX][MAX];
41 int left = 0, right = cellsSize - 1;
42 int result = 0;
43 while (left <= right) {
44 int mid = left + (right - left) / 2;
45 if (canCross(row, col, cells, mid, matrix)) {
46 result = mid;
47 left = mid + 1;
48 } else {
49 right = mid - 1;
50 }
51 }
52 return result + 1;
53}
54
55int main() {
56 int row = 2, col = 2;
57 int cells[4][2] = {{1, 1}, {2, 1}, {1, 2}, {2, 2}};
58 printf("%d\n", latestDayToCross(row, col, cells, 4));
59 return 0;
60}This C implementation utilizes binary search to identify the last day on which a path exists. A DFS is performed on each iteration to verify path connectivity. The matrix is simulated up to the nth day for the selected midpoint during binary search.
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.
Through Java's union-find implementation, every day iterates union operations on flood affected grid cells till connectivity between virtual top and bottom nodes stops. This marks the last possible crossable day.