<p>There is a <strong>1-based</strong> binary matrix where <code>0</code> represents land and <code>1</code> represents water. You are given integers <code>row</code> and <code>col</code> representing the number of rows and columns in the matrix, respectively.</p>

<p>Initially on day <code>0</code>, the <strong>entire</strong> matrix is <strong>land</strong>. However, each day a new cell becomes flooded with <strong>water</strong>. You are given a <strong>1-based</strong> 2D array <code>cells</code>, where <code>cells[i] = [r<sub>i</sub>, c<sub>i</sub>]</code> represents that on the <code>i<sup>th</sup></code> day, the cell on the <code>r<sub>i</sub><sup>th</sup></code> row and <code>c<sub>i</sub><sup>th</sup></code> column (<strong>1-based</strong> coordinates) will be covered with <strong>water</strong> (i.e., changed to <code>1</code>).</p>

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

<p>Return <em>the <strong>last</strong> day where it is possible to walk from the <strong>top</strong> to the <strong>bottom</strong> by only walking on land cells</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/1.png" style="width: 624px; height: 162px;" />
<pre>
<strong>Input:</strong> row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/2.png" style="width: 504px; height: 178px;" />
<pre>
<strong>Input:</strong> row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/27/3.png" style="width: 666px; height: 167px;" />
<pre>
<strong>Input:</strong> row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= row, col &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>4 &lt;= row * col &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>cells.length == row * col</code></li>
	<li><code>1 &lt;= r<sub>i</sub> &lt;= row</code></li>
	<li><code>1 &lt;= c<sub>i</sub> &lt;= col</code></li>
	<li>All the values of <code>cells</code> are <strong>unique</strong>.</li>
</ul>

/////////////////////////////// Preface
// utility functions
using ll = long long;
using ld = long double;
using ull = unsigned long long;

// typedef
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> ti3;
typedef tuple<int, int, int, int> ti4;
typedef tuple<int, int, int, int, int> ti5;
typedef tuple<ll, ll, ll> tll3;
typedef tuple<ll, ll, ll, ll> tll4;
typedef tuple<ll, ll, ll, ll, ll> tll5;
typedef vector<pll> vpll;
typedef array<int, 3> ai3;
typedef array<ll, 3> all3;
typedef array<ll, 4> all4;
typedef array<ll, 5> all5;
typedef vector<all3> vall3;
typedef vector<all4> vall4;
typedef vector<all5> vall5;
typedef pair<ld, ld> pld;
typedef vector<pld> vpld;
typedef vector<ld> vld;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef deque<ll> dqll;
typedef deque<pll> dqpll;
typedef pair<string, string> pss;
typedef vector<pss> vpss;
typedef vector<string> vs;
typedef vector<vs> vvs;
typedef unordered_set<ll> usll;
// typedef unordered_set<pll, PairHash> uspll;
typedef unordered_map<ll, ll> umll;
// typedef unordered_map<pll, ll, PairHash> umpll;

// macros
#define X first
#define Y second

void _p(int x) { cout << x; }
void _p(long x) { cout << x; }
void _p(long long x) { cout << x; }
void _p(unsigned x) { cout << x; }
void _p(unsigned long x) { cout << x; }
void _p(unsigned long long x) { cout << x; }
void _p(float x) { cout << x; }
void _p(double x) { cout << x; }
void _p(long double x) { cout << x; }
void _p(char x) { cout << '\'' << x << '\''; }
void _p(const char *x) { cout << '\"' << x << '\"'; }
void _p(const string &x) { cout << '\"' << x << '\"'; }
void _p(bool x) { cout << (x ? "true" : "false"); }
template <typename A> void _p(const A &x) {
    bool first = true;
    cout << '{';
    for (const auto &i : x) {
        cout << (first ? "" : ","), _p(i);
        first = false;
    }
    cout << '}';
}
template <typename A, typename B> void _p(const pair<A, B> &p) {
    cout << '(';
    _p(p.first);
    cout << ',';
    _p(p.second);
    cout << ')';
}
template <typename... A> void _p(const tuple<A...> &t) {
    bool first = true;
    cout << '(';
    apply(
        [&first](const auto &...args) {
            ((cout << (first ? "" : ","), _p(args), first = false), ...);
        },
        t);
    cout << ')';
}
void _pt(const initializer_list<ll> &t) { _p(tuple(t)); }
template <typename T> void _p(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    _p(debugVector);
}
template <typename T> void _p(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    _p(debugVector);
}
template <typename T, typename... U> void _p(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    _p(debugVector);
}
void __p() { cout << "]\n"; }
template <typename Head, typename... Tail>
void __p(const Head &H, const Tail &...T) {
    _p(H);
    if (sizeof...(T))
        cout << ", ";
    __p(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...)                                                             \
    cout << "Line:" << __LINE__ << " [" << #__VA_ARGS__ << "] = [";            \
    __p(__VA_ARGS__);
#else
#define debug(...)
#endif

#define rep(i, m, n) for (ll i = m; i < n; i++)

template <typename T> void _pn(T &&t) { cout << t << "\n"; }
template <typename T> void _pv(vector<T> v) {
    ll n = v.size();
    rep(i, 0, n) {
        _p(v[i]);
        if (i + 1 != n)
            cout << ' ';
    }
    cout << endl;
}
template <typename T> void _pvv(vector<vector<T>> v) {
    ll n = v.size();
    rep(i, 0, n) _pv(v[i]);
}
template <typename T> void _pvln(vector<T> v) {
    ll n = v.size();
    rep(i, 0, n) cout << v[i] << endl;
}

int mod = 1e9 + 7;

int mod_add(long long a, int b) { return (a + b) % mod; }

int mod_sub(long long a, int b) { return (a + mod - b) % mod; }

int mod_mul(long long a, int b) { return a * b % mod; }

int mod_pow(int b, int p) {
    if (!p)
        return 1;
    int half = mod_pow(b, p / 2);
    return mod_mul(mod_mul(half, half), p % 2 ? b : 1);
}

int mod_inv(int b) { return mod_pow(b, mod - 2); }

int mod_factorial(int x) {
    if (x < 2)
        return 1;
    return mod_mul(x, mod_factorial(x - 1));
}
/////////////////////////////// Preface

struct UnionFind {
    vector<int> p, r;
    UnionFind(int sz) : p(sz), r(sz) {
        iota(p.begin(), p.end(), 0);
        fill(r.begin(), r.end(), 1);
    }
    int find(int i) {
        if (i != p[i])
            p[i] = find(p[i]);
        return p[i];
    }
    bool is_connected(int u, int v) { return find(u) == find(v); }
    void connect(int u, int v) {
        if (is_connected(u, v))
            return;
        int pu = find(u), pv = find(v);
        if (r[pu] < r[pv]) // pu is parent.
            swap(pu, pv);
        r[pu] += r[pv];
        p[pv] = pu;
    }
};

vpii dirs{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int to1d(int r, int c, int col) { return r * col + c; }

class Solution {
  public:
    int latestDayToCross(int row, int col, vector<vector<int>> &cells) {
        int n = cells.size(), l = 0, r = n - 1, ans = -1, sz = row * col;
        auto ok = [&](int m) {
            UnionFind uf(sz + 2);
            vvi g(row, vi(col));
            for (int i = 0; i < m; ++i) {
                int r = cells[i][0] - 1, c = cells[i][1] - 1;
                g[r][c] = 1;
            }
            for (int r = 0; r < row; ++r)
                for (int c = 0; c < col; ++c)
                    if (!g[r][c])
                        for (auto [rd, cd] : dirs) {
                            int rn = r + rd, cn = c + cd;
                            if (0 <= rn && rn < row && 0 <= cn && cn < col &&
                                !g[rn][cn])
                                uf.connect(to1d(r, c, col), to1d(rn, cn, col));
                        }
            int src = sz, dst = sz + 1;
            for (int c = 0; c < col; ++c)
                if (!g[0][c])
                    uf.connect(src, to1d(0, c, col));
            for (int c = 0; c < col; ++c)
                if (!g[row - 1][c])
                    uf.connect(dst, to1d(row - 1, c, col));
            return uf.is_connected(src, dst);
        };
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (ok(m)) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return ans;
    }
};
206209