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

INF=1000000000
class Solution:
    def update(self, i,j,Q,current_d,d_to_fire):
        m=len(d_to_fire)
        n=len(d_to_fire[0])
        if i<0 or i>=m or j<0 or j>=n:
            return
        if d_to_fire[i][j]!=-1:
            return
        d_to_fire[i][j]=current_d
        Q.append((i,j))
        return False
    
    def bfs(self, fires, grid,d_to_fire):
        m=len(grid)
        n=len(grid[0])
        Q=collections.deque()
        Q.extend(fires)
        while Q:
            i,j=Q.popleft()
            self.update(i+1,j,Q,d_to_fire[i][j]+1,d_to_fire)
            self.update(i-1,j,Q,d_to_fire[i][j]+1,d_to_fire)
            self.update(i,j+1,Q,d_to_fire[i][j]+1,d_to_fire)
            self.update(i,j-1,Q,d_to_fire[i][j]+1,d_to_fire)
        return
    def is_safehouse(self, i,j,grid,d,Q,current_d,d_to_fire):
        m=len(grid)
        n=len(grid[0])
        if i<0 or i>=m or j<0 or j>=n:
            return False
        if d[i][j]>=0:
            return False
        if grid[i][j]==2:
            return False
        if i==m-1 and j==n-1 and d_to_fire[i][j]>=current_d:
            return True
        if d_to_fire[i][j]<=current_d:
            return False
        d[i][j]=current_d
        Q.append((i,j))
        return False
    def possible(self,grid,d_to_fire,initial_time):
        m=len(grid)
        n=len(grid[0])
        d=[[-1 for _ in range(n)] for _ in range(m)]
        Q=collections.deque()
        Q.append((0,0))
        d[0][0]=initial_time
        while Q:
            i,j=Q.popleft()
            current_d=min(d[i][j]+1,INF)
            if self.is_safehouse(i+1,j,grid,d,Q,current_d,d_to_fire) or self.is_safehouse(i-1,j,grid,d,Q,current_d,d_to_fire) or self.is_safehouse(i,j+1,grid,d,Q,current_d,d_to_fire) or self.is_safehouse(i,j-1,grid,d,Q,current_d,d_to_fire):
                return True
        return False
    def maximumMinutes(self, grid: List[List[int]]) -> int:
        m=len(grid)
        n=len(grid[0])
        d_to_fire=[[-1 for _ in range(n)] for _ in range(m)]
        fires=[]
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    d_to_fire[i][j]=0
                    fires.append((i,j))
                if grid[i][j]==2:
                    d_to_fire[i][j]=INF+1
        self.bfs(fires,grid,d_to_fire)
        for i in range(m):
            for j in range(n):
                if d_to_fire[i][j]==-1:
                    d_to_fire[i][j]=INF+1
        if not self.possible(grid,d_to_fire,0):
            return -1
        if self.possible(grid,d_to_fire,INF):
            return INF
        l=0
        r=INF
        while l<r-1:
            mid=(l+r)//2
            if self.possible(grid,d_to_fire,mid):
                l=mid
            else:
                r=mid
        return l
18500