<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:
        """Solution 1:"""
        def find(x):
            if x == parents[x]:
                return x
            res = find(parents[x])
            parents[x] = res
            return res
        
        def union(x, y):
            anc_x, anc_y = find(x), find(y)
            if anc_x == anc_y:
                return
            if ranks[anc_x] > ranks[anc_y]:
                parents[anc_y] = anc_x
            elif ranks[anc_x] < ranks[anc_y]:
                parents[anc_x] = anc_y
            else:
                parents[anc_y] = anc_x
                ranks[anc_x] += 1
        
        parents = {}
        ranks = collections.defaultdict(int)

        land_set = set()
        dummy1, dummy2 = "d1", "d2"
        parents[dummy1], parents[dummy2] = "d1", "d2"
        
        for idx in range(len(cells) - 1, -1, -1):
            w_i, w_j = cells[idx][0] - 1, cells[idx][1] - 1
            land_set.add((w_i, w_j))
            parents[(w_i, w_j)] = (w_i, w_j)

            for x, y in self.neighbors(w_i, w_j, row, col):
                if (x, y) in land_set:
                    union((x, y), (w_i, w_j))
            
            if w_i == 0:
                union((w_i, w_j), dummy1)
            if w_i == row - 1:
                union((w_i, w_j), dummy2)
            
            if find(dummy1) == find(dummy2):
                return idx
        return 0
            
    def neighbors(self, i, j, row, col):
        res = []
        dirs = [(0, 1), (-1, 0), (1, 0), (0, -1)]
        for x, y in dirs:
            u, v = i + x, j + y
            if 0 <= u < row and 0 <= v < col:
                res.append((u, v))
        return res


    #     """Solution 2:"""
    #     # below is brute force and results in TLE
    #     # res = 0
    #     # for t in range(1, row * col + 1):
    #     #     if not self.solve_once(row, col, cells, t):
    #     #         return res
    #     #     res += 1
    #     # return

    # #     left, right = 1, row * col
    # #     while left < right - 1:
    # #         mid = (left + right) // 2
    # #         if self.solve_once(row, col, cells, mid):
    # #             left = mid
    # #         else:
    # #             right = mid - 1
    # #     if self.solve_once(row, col, cells, right):
    # #         return right
    # #     return left

    # # def solve_once(self, row, col, cells, t):
    # #     rained_on = set()
    # #     for i in range(t):
    # #         x, y = cells[i]
    # #         rained_on.add((x - 1, y - 1))

    # #     seen = set()
    # #     for j in range(col):
    # #         curr = (0, j)
    # #         if curr not in seen and curr not in rained_on:
    # #             seen.add(curr)
    # #             if self.dfs(curr, row, col, rained_on, seen):
    # #                 return True
    # #     return False
        
    # # def dfs(self, curr, row, col, rained_on, seen):
    # #     if curr[0] == row - 1:
    # #         return True
    # #     for neighbor in self.get_neighbors(curr, row, col, rained_on):
    # #         if neighbor not in seen:
    # #             seen.add(neighbor)
    # #             reached = self.dfs(neighbor, row, col, rained_on, seen)
    # #             if reached:
    # #                 return True
    # #     return False

    # # def get_neighbors(self, curr, row, col, rained_on):
    # #     i, j = curr
    # #     res = []

    # #     if i + 1 < row and (i + 1, j) not in rained_on:
    # #         res.append((i + 1, j))
    # #     if i - 1 >= 0 and (i - 1, j) not in rained_on:
    # #         res.append((i - 1, j))
    # #     if j + 1 < col and (i, j + 1) not in rained_on:
    # #         res.append((i, j + 1))
    # #     if j - 1 >= 0 and (i, j - 1) not in rained_on:
    # #         res.append((i, j - 1))
        
    # #     return res
32800