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

#include <vector>

using namespace std;

class Solution {
public:
    // Parent array for Disjoint Set data structure (Union-Find)
    vector<int> parent;
    // Array to represent the four directional moves (left, right, down, up)
    int dirs[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
    // Member variables to store the number of rows and columns of the grid
    int totalRows, totalCols;

    // Method to determine the latest day it's possible to cross the river
    int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
        // Total number of cells and setting class variables
        int totalCells = row * col;
        totalRows = row;
        totalCols = col;
        // Resize parent array to accommodate all cells and two virtual nodes
        parent.resize(totalCells + 2);

        // Initialize the parent array such that each node is its own parent
        for (int i = 0; i < parent.size(); ++i) {
            parent[i] = i;
        }

        // Grid to keep track of the filled cells
        vector<vector<bool>> grid(row, vector<bool>(col, false));
        // Define two virtual nodes representing the top and bottom of the grid
        int virtualTop = totalCells, virtualBottom = totalCells + 1;

        // Iterate from the last day to the first (reverse flooding)
        for (int k = cells.size() - 1; k >= 0; --k) {
            // Get the actual row and column index from the cells vector
            int i = cells[k][0] - 1, j = cells[k][1] - 1;
            // Fill the cell
            grid[i][j] = true;

            // Connect the current cell with its adjacent filled cells
            for (auto &dir : dirs) {
                // Check if an adjacent cell is filled and valid
                if (isValid(i + dir[0], j + dir[1], grid)) {
                    // Union-find merge operation
                    parent[find(i * col + j)] = find((i + dir[0]) * col + j + dir[1]);
                }
            }

            // Connect the current cell to the virtual top if it's on the first row
            if (i == 0) {
                parent[find(i * col + j)] = find(virtualTop);
            }
            // Connect the current cell to the virtual bottom if it's on the last row
            if (i == row - 1) {
                parent[find(i * col + j)] = find(virtualBottom);
            }

            // If virtual top and bottom are connected, it's possible to cross the grid, return the day
            if (find(virtualTop) == find(virtualBottom)) {
                return k;
            }
        }
        // If no such day exists, return 0
        return 0;
    }

    // Helper function to check if a cell is within the grid bounds and is filled
    bool isValid(int i, int j, vector<vector<bool>>& grid) {
        return i >= 0 && i < totalRows && j >= 0 && j < totalCols && grid[i][j];
    }

    // Union-Find 'find' operation with path compression
    int find(int x) {
        // Recursively find the ultimate parent of x
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
};
110160