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

from collections import deque
from typing import List

class Solution:
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        
        def valid(row, col):
            return 0 <= row < n_rows and 0 <= col < n_cols

        # Check if you can safely reach the safehouse with k minutes of delay
        def check(k):
            seen = set([(0, 0)])
            queue = deque([(0, 0, k)])  # BFS approach
            
            while queue:
                row, col, sec = queue.popleft()

                # If we reached the safehouse and it's safe
                if row == n_rows - 1 and col == n_cols - 1:
                    return True
                
                for dy, dx in directions:
                    new_row, new_col = row + dy, col + dx

                    if valid(new_row, new_col) and (new_row, new_col) not in seen:
                        if sec + 1 < fire_time[new_row][new_col]:
                            seen.add((new_row, new_col))
                            queue.append((new_row, new_col, sec + 1))
                        elif new_row == n_rows - 1 and new_col == n_cols - 1 and sec + 1 == fire_time[new_row][new_col]:
                            return True
            
            return False

        n_rows, n_cols = len(grid), len(grid[0])

        fire_time = [[float('inf')] * n_cols for _ in range(n_rows)]  # Holds time fire reaches each cell

        fire_queue = deque()

        # Initialize fire times and fire BFS queue
        for i in range(n_rows):
            for j in range(n_cols):
                if grid[i][j] == 1:  # Fire
                    fire_time[i][j] = 0
                    fire_queue.append((i, j, 0))  # (row, col, time)
                elif grid[i][j] == 2:  # Wall
                    fire_time[i][j] = -1  # Wall is unreachable for both fire and person

        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        # BFS to propagate fire
        while fire_queue:
            row, col, time = fire_queue.popleft()
            for dy, dx in directions:
                new_row, new_col = row + dy, col + dx
                if valid(new_row, new_col) and fire_time[new_row][new_col] == float('inf') and grid[new_row][new_col] == 0:
                    fire_time[new_row][new_col] = time + 1
                    fire_queue.append((new_row, new_col, time + 1))

        # BFS to check if the person can reach the safehouse without delay
        check_queue = deque([(0, 0)])
        check_seen = set([(0, 0)])
        
        while check_queue:
            row, col = check_queue.popleft()

            if row == n_rows - 1 and col == n_cols - 1:  # Already reachable at the beginning
                return int(1e9)  # Safe regardless of delay

            for dy, dx in directions:
                new_row, new_col = row + dy, col + dx
                if valid(new_row, new_col) and (new_row, new_col) not in check_seen:
                    if fire_time[new_row][new_col] == float('inf'):
                        check_seen.add((new_row, new_col))
                        check_queue.append((new_row, new_col))

        # Binary search for the maximum delay
        left, right = 0, n_rows * n_cols

        while left <= right:
            mid = (left + right) // 2

            if check(mid):  # If it's safe with this delay
                left = mid + 1
            else:
                right = mid - 1

        return right if right >= 0 else -1

18700