Formatted question description: https://leetcode.ca/all/1970.html

# 1970. Last Day Where You Can Still Cross

## Level

Hard

## Description

There is a **1-based** binary matrix where `0`

represents land and `1`

represents water. You are given integers `row`

and `col`

representing the number of rows and columns in the matrix, respectively.

Initially on day `0`

, the **entire** matrix is **land**. However, each day a new cell becomes flooded with **water**. You are given a **1-based** 2D array `cells`

, where `cells[i] = [r_i, c_i]`

represents that on the `i-th`

day, the cell on the `r_i-th`

row and `c_i-th`

column (**1-based** coordinates) will be covered with **water** (i.e., changed to 1).

You want to find the **last** day that it is possible to walk from the **top** to the **bottom** by only walking on land cells. You can start from **any** cell in the top row and end at **any** cell in the bottom row. You can only travel in the **four** cardinal directions (left, right, up, and down).

Return *the last day where it is possible to walk from the top to the bottom by only walking on land cells*.

**Example 1:**

**Input:** row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]

**Output:** 2

**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 2.

**Example 2:**

**Input:** row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]

**Output:** 1

**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 1.

**Example 3:**

**Input:** row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]

**Output:** 3

**Explanation:** The above image depicts how the matrix changes each day starting from day 0.
The last day where it is possible to cross from top to bottom is on day 3.

**Constraints:**

`2 <= row, col <= 2 * 10^4`

`4 <= row * col <= 2 * 10^4`

`cells.length == row * col`

`1 <= r_i <= row`

`1 <= c_i <= col`

- All the values of
`cells`

are**unique**.

## Solution

The maximum possible value of last day is `row * col - 1`

and the minimum possible value of last day is `col - 1`

. Use binary search to find the last day. Each time let `mid`

be the mean of `high`

and `low`

, apply the first `mid`

elements in `cells`

as water cells, and check whether it is possible to walk from top to bottom.

```
class Solution {
static final int WATER = -1;
static final int WHITE = 0;
static final int BLACK = 1;
int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
public int latestDayToCross(int row, int col, int[][] cells) {
int low = col - 1, high = row * col - 1;
while (low < high) {
int mid = (high - low + 1) / 2 + low;
boolean canCross = check(row, col, cells, mid);
if (canCross)
low = mid;
else
high = mid - 1;
}
return low;
}
public boolean check(int row, int col, int[][] cells, int mid) {
int[][] grid = new int[row][col];
for (int i = 0; i < mid; i++) {
int[] cell = cells[i];
grid[cell[0] - 1][cell[1] - 1] = WATER;
}
Queue<int[]> queue = new LinkedList<int[]>();
for (int j = 0; j < col; j++) {
if (grid[0][j] == WHITE) {
grid[0][j] = BLACK;
queue.offer(new int[]{0, j});
}
}
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
for (int[] direction : directions) {
int newR = r + direction[0], newC = c + direction[1];
if (newR >= 0 && newR < row && newC >= 0 && newC < col && grid[newR][newC] == WHITE) {
if (newR == row - 1)
return true;
grid[newR][newC] = BLACK;
queue.offer(new int[]{newR, newC});
}
}
}
return false;
}
}
```