<p>You are given an <code>n x n</code> integer matrix <code>grid</code> where each value <code>grid[i][j]</code> represents the elevation at that point <code>(i, j)</code>.</p>

<p>The rain starts to fall. At time <code>t</code>, the depth of the water everywhere is <code>t</code>. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most <code>t</code>. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.</p>

<p>Return <em>the least time until you can reach the bottom right square </em><code>(n - 1, n - 1)</code><em> if you start at the top left square </em><code>(0, 0)</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/swim1-grid.jpg" style="width: 164px; height: 165px;" />
<pre>
<strong>Input:</strong> grid = [[0,2],[1,3]]
<strong>Output:</strong> 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/29/swim2-grid-1.jpg" style="width: 404px; height: 405px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
<strong>Output:</strong> 16
<strong>Explanation:</strong> The final route is shown.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
</pre>

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

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n &lt;= 50</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;&nbsp;n<sup>2</sup></code></li>
	<li>Each value <code>grid[i][j]</code> is <strong>unique</strong>.</li>
</ul>

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        if len(grid)  == 1:
            return grid[0][0]
        
        mydict = []
        
        def nextmove(x,y):
            output = []
            if x+1 <= len(grid) -1  :
                output.append([x+1 , y])
            if x-1>=0  : 
                output.append([x-1 , y])
            if y+1 <= len(grid) -1  : 
                output.append([x , y +1])
            if y-1>=0  :
                output.append([x , y-1])
            return output
        
        visited = [[0,0]]
        options = []
        options.append([0,0])
        print("nextmove",nextmove(0,0))
        for a,b in nextmove(0,0):
            heapq.heappush(mydict,[grid[a][b] , [a,b]])
            options.append([a,b])
        mintime = grid[0][0]
        # print(mydict)
        while True:
            # print(mydict)
            if len(mydict) ==0:
                # print("error")
                break
            distance , [x_pos, y_pos] = heapq.heappop(mydict)   # distance , [x_pos, y_pos]
            mintime = max(distance ,mintime ) 
            # mintime = min(mintime , distance)
            # print(f"distance:{distance} ,[x_pos, y_pos] , [{x_pos}, {y_pos}], mintime:{mintime} ")
            visited.append( [x_pos, y_pos] )
            
            if x_pos == len(grid) -1 and y_pos == len(grid) -1:
                mintime = max(distance ,mintime )
                return mintime
                
            for a,b in nextmove(x_pos,y_pos): 
                if [a,b] not in options:
                    # print("a,b",a,b, len(grid) -1)
                    heapq.heappush(mydict,[grid[a][b] , [a,b]])
                    if a ==b and a == len(grid) -1:
                        # print("done")
                        mintime = max(grid[a][b] ,mintime ) 
                        # print(mintime)
                        return mintime
                    options.append([a,b])
            # print("**end: ",mydict, mintime)
        return mintime
                        
                    
            
            
            
            
                
        
        
17500