<p>You are given a <strong>0-indexed</strong> 2D integer array <code>grid</code> of size <code>m x n</code> which represents a field. Each cell has one of three values:</p>

<ul>
	<li><code>0</code> represents grass,</li>
	<li><code>1</code> represents fire,</li>
	<li><code>2</code> represents a wall that you and fire cannot pass through.</li>
</ul>

<p>You are situated in the top-left cell, <code>(0, 0)</code>, and you want to travel to the safehouse at the bottom-right cell, <code>(m - 1, n - 1)</code>. Every minute, you may move to an <strong>adjacent</strong> grass cell. <strong>After</strong> your move, every fire cell will spread to all <strong>adjacent</strong> cells that are not walls.</p>

<p>Return <em>the <strong>maximum</strong> number of minutes that you can stay in your initial position before moving while still safely reaching the safehouse</em>. If this is impossible, return <code>-1</code>. If you can <strong>always</strong> reach the safehouse regardless of the minutes stayed, return <code>10<sup>9</sup></code>.</p>

<p>Note that even if the fire spreads to the safehouse immediately after you have reached it, it will be counted as safely reaching the safehouse.</p>

<p>A cell is <strong>adjacent</strong> to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/10/ex1new.jpg" style="width: 650px; height: 404px;" />
<pre>
<strong>Input:</strong> grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The figure above shows the scenario where you stay in the initial position for 3 minutes.
You will still be able to safely reach the safehouse.
Staying for more than 3 minutes will not allow you to safely reach the safehouse.</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/10/ex2new2.jpg" style="width: 515px; height: 150px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> The figure above shows the scenario where you immediately move towards the safehouse.
Fire will spread to any cell you move towards and it is impossible to safely reach the safehouse.
Thus, -1 is returned.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/10/ex3new.jpg" style="width: 174px; height: 150px;" />
<pre>
<strong>Input:</strong> grid = [[0,0,0],[2,2,0],[1,2,0]]
<strong>Output:</strong> 1000000000
<strong>Explanation:</strong> The figure above shows the initial grid.
Notice that the fire is contained by walls and you will always be able to safely reach the safehouse.
Thus, 10<sup>9</sup> is returned.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>2 &lt;= m, n &lt;= 300</code></li>
	<li><code>4 &lt;= m * n &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>grid[i][j]</code> is either <code>0</code>, <code>1</code>, or <code>2</code>.</li>
	<li><code>grid[0][0] == grid[m - 1][n - 1] == 0</code></li>
</ul>

class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        """
        Initial thought:
                    
        You could bfs from the fires, then perform a DFS to check if you can make it.
        Hard to binary search, since we need to track the state of the board
        
        ACTUALLY—just use a time to track the values and binary search.
            
        O(m^2n^2) time complexity, since 0 <= res <= O(mn).
        
        Can we optimize?
        
        1) we could try bfs to see where you could be at any given time, and use the queue.
            Note that this could require some machinery: require bfs'ing over time?
            
            ACTUALLY: THIS IS THE CORRECT SOLUTION: TWO BFS.
         
        Consider any path from exit to current.
        
        For each path, the maximum amount of time you can take this path is the time until a fire reaches any point on the path (edge case for the last point).
        
        Therefore: frame this in terms of a max min problem: max over the minimum of all paths.
         
        BETTER:
        If the fire reaches the house before you, return -1.
        
        otherwise: there exists some path.
        
        If the fire reaches any point along the path before you or at the same time, you lose.
        
        
        bfs edge case: 
        
        If both parties arrive at the same time: then we're safe. However, we can't have these two parties cross somewhere along the path.
        
        How would we know? Well: suppose they both cross at some point. Then: the sortest path must have been the same, up to diagonals.
        
        Therefore: just need to check the last two grids.
        
        Let's say we update fire grid:
            Check:
                a) haven't visited yet.
            
        Let's say we update people grid:
            Check:
                a) haven't visited yet
                b) time < fire, UNLESS, we are at the last place; otherwise >=
        """
        max_time = 10**9
        m, n = len(grid), len(grid[0])
        
        def bfs(q, curr_grid, is_fire):
            while q:
                r, c = q.popleft()
                if (r, c) == (m-1, n-1):
                    return
                for dr, dc in [(r+1,c), (r-1,c), (r,c+1), (r,c-1)]:
                    if 0 <= dr < m and 0 <= dc < n and grid[dr][dc] != 2 and curr_grid[dr][dc] == max_time:
                        if is_fire or (dr == m-1 and dc == n-1 and curr_grid[r][c] + 1 <= fire_grid[dr][dc]) or ((dr < m or dc < n) and curr_grid[r][c] + 1 < fire_grid[dr][dc]):
                            curr_grid[dr][dc] = curr_grid[r][c] + 1 # update distances.
                            q.append((dr, dc))

        person_q = deque([(0, 0)])
        fire_q = deque([])

        person_grid = [[max_time] * n for _ in range(m)]
        person_grid[0][0] = 0
        
        fire_grid = [[max_time] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    fire_grid[i][j] = 0 # starting point.
                    fire_q.append((i, j))
        
        bfs(fire_q, fire_grid, True)
        bfs(person_q, person_grid, False)
                
        from pprint import pprint
        pprint(person_grid)
        pprint(fire_grid)
            
        if person_grid[-1][-1] == max_time:
            return -1
        elif fire_grid[-1][-1] == max_time:
            return max_time
        
        diff = fire_grid[-1][-1] - person_grid[-1][-1]
        if diff == 0:
            return 0
        
        # have two paths to exit.
        path1, path2 = person_grid[-1][-2], person_grid[-2][-1]
        diff1, diff2 = fire_grid[-1][-2] - path1, fire_grid[-2][-1] - path2
        if path1 >= 0 and path2 >= 0 and (diff1 > diff or diff2 > diff):
            return diff
        
        return diff - 1
18900