[1970. Last Day Where You Can Still Cross](https://leetcode.com/problems/last-day-where-you-can-still-cross/)

### 題目描述

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] = [ri, ci]` represents that on the i^th^ day, the cell on the ri^th^ row and ci^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 <= `ri` <= `row`
* 1 <= `ci` <= `col`
* All the values of `cells` are **unique**.

### 解答

#### C++

class Solution {
public:
    const int LAND = 0;
    const int WATER = 1;
    const int VISITED = 2;
    vector<pair<int, int>> delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        ios_base::sync_with_stdio(0); cin.tie(0);
        int num_day = row * col;
        return binarySearch(num_day, row, col, cells);
    }

    int binarySearch(int num_day, int m, int n, vector<vector<int>>& cells) {
        int left = 0, right = num_day;
        while (left < right) {
            int mid = left + (right - left) / 2;
            bool reachable = isReachable(mid, m, n, cells);
            // cout << "\tmid = " << mid << "\treachable = " << reachable << endl;
            if (reachable) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right - 1;
    }

    bool isReachable(int nth_day, int m, int n, vector<vector<int>>& cells) {
        vector<vector<int>> grid(m, vector<int>(n, LAND));
        queue<pair<int, int>> frontier;
        for (int i = 0; i < nth_day; i ++) {
            grid[cells[i][0] - 1][cells[i][1] - 1] = WATER;
        }
        for (int c = 0; c < n; c ++) {
            if (grid[0][c] == LAND) {
                frontier.push({0, c});
                grid[0][c] = VISITED;
            }
        }
        while (not frontier.empty()) {
            const auto [r, c] = frontier.front();
            frontier.pop();
            // printf("\t(%d, %d)", r, c);
            for (const auto [dr, dc] : delta) {
                if (r + dr < 0 or r + dr >= m or \
                    c + dc < 0 or c + dc >= n or \
                    grid[r + dr][c + dc] != LAND) {
                        continue;
                }
                grid[r + dr][c + dc] = VISITED;
                if (r + dr == m - 1) {
                    return true;
                }
                frontier.push({r + dr, c + dc});
            }
        }
        return false;
    }
};

Binary Search + BFS

> [name=Jerry Wu][time=30 June, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)