<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>

class UnionFindLandMatrix {
private:
    const int NULL_NODE = -1;
    unordered_map<int, int> node2Parent;
    unordered_map<int, int> sizeOfSet;
public:
    UnionFindLandMatrix() {
        this->node2Parent = {};
        this->sizeOfSet = {};
    }

    void addNode(const int node) {
        if (!this->node2Parent.count(node)) {
            this->node2Parent[node] = NULL_NODE;
            this->sizeOfSet[node] = 1;
        }
    }

    int findRoot(int node) {
        int root = node;
        while (this->node2Parent[root] != NULL_NODE) {
            root = this->node2Parent[root];
        }
        while (node != root) {
            const int prev = node;
            node = this->node2Parent[node];
            this->node2Parent[prev] = root;
        }
        return root;
    }

    void merge(const int x, const int y) {
        const int rootX = this->findRoot(x);
        const int rootY = this->findRoot(y);
        if (rootX != rootY) {
            this->node2Parent[rootY] = rootX;
            this->sizeOfSet[rootX] += this->sizeOfSet[rootY];
            this->sizeOfSet.erase(rootY);
        }
    }

    bool isConnected(const int x, const int y) {
        return findRoot(x) == findRoot(y);
    }

    int getSizeOfSet(const int node) {
        return this->sizeOfSet[this->findRoot(node)];
    }
};

class Solution {
    typedef vector<int> VI; typedef vector<VI> VVI;
    const int LAND = 0; const int WATER = 1;
    const int MATRIX_TOP = -2; const int MATRIX_BOTTOM = -3;
    const VI dx = {-1, 1, 0, 0}; const VI dy = {0, 0, -1, 1};
    int row; int col;
public:
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        if (row == 0 || col == 0) 
            return -1;

        this->row = row;
        this->col = col;
        int days = (int)cells.size();
        VVI matrix(row, VI(col, LAND));
        UnionFindLandMatrix uf;

        // generate final state and initialize the union find set
        this->init(matrix, cells, uf);
        
        // reversely iterate
        for (int i = days-1; i >= 0; --i) {
            const int x = cells[i][0];
            const int y = cells[i][1];
            const int currNode = x*this->col + y;
            
            // alter matrix and update the UF
            matrix[x][y] = LAND;
            uf.addNode(currNode);
            if (x == 0) // connect to the virtual TOP
                uf.merge(currNode, MATRIX_TOP);
            if (x == this->row-1) // connect to the virtual BOTTOM
                uf.merge(currNode, MATRIX_BOTTOM);
            
            this->unionNeighbors(x, y, uf, matrix);

            // check if top and bottom are connected
            if (uf.isConnected(MATRIX_TOP, MATRIX_BOTTOM))
                return i;
        }

        return 1;
    }
private:
    void init(VVI& matrix, VVI& cells, UnionFindLandMatrix& uf) {
        for (VI& cell : cells) {
            const int x = --cell[0];
            const int y = --cell[1];
            matrix[x][y] = WATER;
        } // final state

        // add all nodes
        uf.addNode(MATRIX_TOP);
        uf.addNode(MATRIX_BOTTOM);
        for (int x = 0; x < this->row; ++x) {
            for (int y = 0; y < this->col; ++y) {
                if (matrix[x][y] == WATER) continue;
                // add node if it's LAND
                const int node = x*this->col + y;
                uf.addNode(node);
                if (x == 0)
                    uf.merge(node, MATRIX_TOP);
                if (x == this->row-1)
                    uf.merge(node, MATRIX_BOTTOM);
            }
        }

        // merge nodes
        for (int x = 0; x < this->row; ++x) {
            for (int y = 0; y < this->col; ++y) {
                if (matrix[x][y] == WATER) continue;
                this->unionNeighbors(x, y, uf, matrix);
            }
        }
    }

    void unionNeighbors(const int x, const int y, UnionFindLandMatrix& uf, const VVI& matrix) {
        const int currNode = x*this->col + y;
        for (int i = 0; i < 4; ++i) {
            const int nextX = x + this->dx[i];
            const int nextY = y + this->dy[i];
            const int nextNode = nextX*this->col + nextY;
            if (isValidNode(nextX, nextY, matrix))
                uf.merge(currNode, nextNode);
        }
    }

    bool isValidNode(const int x, const int y, const VVI& matrix) {
        if (x < 0 || y < 0 || x >= this->row || y >= this->col)
            return false;
        return matrix[x][y] == LAND;
    }
};
133029