<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 Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def find(x, parent):
            if parent[x] != x:
                parent[x] = find(parent[x], parent)
            return parent[x]
        
        def union(x, y, parent, size):
            root_x = find(x, parent)
            root_y = find(y, parent)
            if root_x != root_y:
                if size[root_x] < size[root_y]:
                    parent[root_x] = root_y
                    size[root_y] += size[root_x]
                else:
                    parent[root_y] = root_x
                    size[root_x] += size[root_y]
        
        # Initialize union-find data structures
        parent = [i for i in range(row * col + 2)]
        size = [1] * (row * col + 2)
        grid = [[1] * col for _ in range(row)]
        
        # Constants for virtual top and bottom nodes
        TOP = row * col
        BOTTOM = row * col + 1
        
        # Directions for neighbors
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        # Binary search on days
        left, right = 0, len(cells) - 1
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            can_cross = False
            
            # Reinitialize grid and union-find for each mid
            for i in range(row):
                for j in range(col):
                    grid[i][j] = 1
            for i in range(row * col + 2):
                parent[i] = i
                size[i] = 1
            
            # Flood cells up to mid
            for i in range(mid + 1):
                r, c = cells[i]
                grid[r - 1][c - 1] = 0
            
            # Connect adjacent land cells in the grid
            for i in range(row):
                for j in range(col):
                    if grid[i][j] == 1:
                        for di, dj in directions:
                            ni, nj = i + di, j + dj
                            if 0 <= ni < row and 0 <= nj < col and grid[ni][nj] == 1:
                                union((i * col) + j, (ni * col) + nj, parent, size)
            
            # Connect top row cells to virtual top node
            for j in range(col):
                if grid[0][j] == 1:
                    union(TOP, j, parent, size)
            
            # Connect bottom row cells to virtual bottom node
            for j in range(col):
                if grid[row - 1][j] == 1:
                    union(BOTTOM, (row - 1) * col + j, parent, size)
            
            # Check if top and bottom are connected
            if find(TOP, parent) == find(BOTTOM, parent):
                can_cross = True
            
            if can_cross:
                result = mid + 1
                left = mid + 1
            else:
                right = mid - 1
        
        return result

# Example usage:
solution = Solution()
row = 2
col = 2
cells = [[1,1],[2,1],[1,2],[2,2]]
print(solution.latestDayToCross(row, col, cells))  # Output: 2
3555