<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:
        left = 0
        right = len(cells)

        # # floodedDict[t] contains set of flooded cells on day t
        # floodedDict = defaultdict(set) # O(cells^2 ) space
        # for i in range(1, len(cells)+1): # O(cells^2) time complexity
        #     for j in range(i):
        #         floodedDict[i].add(tuple(cells[j]))


        # return true if it is possible to go from (0,0) to (r-1, c-1)
        # on a specific day
        def check(row, col, cells, t):
            # do dfs on cells as if it is a graph
            # if we can reach (r,c), then it is possible to get there on day t
            flooded = set() # O(cells) space
            for i in range(t): # O(cells)
                flooded.add(tuple(cells[i]))


            # keep track of what we have seen, and pass in a set
            # of flooded tiles for this day
            def dfs(row, col, cells, x, y, seen, flooded):
                for i,j in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
                    if 0 <= i < row and 0 <= j < col: # check if within bounds
                        if (i+1,j+1) not in seen and (i+1,j+1) not in flooded:
                            seen.add((i+1,j+1))
                            dfs(row, col, cells, i, j, seen, flooded)

            seen = set()
        
            # check if top row can be added, since we can start from
            # any where on top
            for i in range(col): # O(row*col)
                if (1,i+1) not in flooded:
                    seen.add((1,i+1))
                    dfs(row, col, cells, 0, i, seen, flooded)

            # return true if any of the bottom row is seen
            for i in range(col):
                if (row, i+1) in seen:
                    return True
            return False

        while left <= right: # O( (cells + (row*col)) * ( log cells))
            mid = (left+right)//2
            if check(row, col, cells, mid):
                left = mid + 1
            else:
                right = mid - 1
        return right
2940