


from heapq import heappop, heappush

import numpy as np
def 	_UpperCamelCase					(    lowerCAmelCase_	,    lowerCAmelCase_	,    lowerCAmelCase_	,    lowerCAmelCase_	,    )    ->Tuple:
   UpperCAmelCase					,	UpperCAmelCase      					=  grid.shape
   UpperCAmelCase      					=  [-1, 1, 0, 0]
   UpperCAmelCase      					=  [0, 0, -1, 1]
   if allow_diagonal:
      dx += [-1, -1, 1, 1]
      dy += [-1, 1, -1, 1]

   UpperCAmelCase					,	UpperCAmelCase      					=  [(0, source)], set()
   UpperCAmelCase      					=  np.full((rows, cols)	,    np.inf )
   UpperCAmelCase      					=  0
   UpperCAmelCase      					=  np.empty((rows, cols)	,    dtype=__snake_case )
   UpperCAmelCase      					=  None

   while queue:
      ((UpperCAmelCase)					,	(UpperCAmelCase))      					=  heappop(__snake_case )
      if (x, y) in visited:
         continue
      visited.add((x, y) )

      if (x, y) == destination:
         UpperCAmelCase      					=  []
         while (x, y) != source:
            path.append((x, y) )
            UpperCAmelCase					,	UpperCAmelCase      					=  predecessors[x, y]
         path.append(__snake_case )  # add the source manually
         path.reverse()
         return matrix[destination], path

      for i in range(len(__snake_case ) ):
         UpperCAmelCase					,	UpperCAmelCase      					=  x + dx[i], y + dy[i]
         if 0 <= nx < rows and 0 <= ny < cols:
            UpperCAmelCase      					=  grid[nx][ny]
            if next_node == 1 and matrix[nx, ny] > dist + 1:
               heappush(__snake_case	,    (dist + 1, (nx, ny)) )
               UpperCAmelCase      					=  dist + 1
               UpperCAmelCase      					=  (x, y)

   return np.inf, []


if __name__ == "__main__":
 import doctest

 doctest.testmod()











from __future__ import annotations





def    __lowerCAmelCase   (    __snake_case							):
     __lowerCAmelCase             =       len(__snake_case							)
     # We need to create solution object to save path.
     __lowerCAmelCase             =       [[0 for _ in range(__snake_case							)] for _ in range(__snake_case							)]
     __lowerCAmelCase             =       run_maze(__snake_case       ,			0       ,			0       ,			__snake_case							)
     if solved:
          print("\n".join(str(__snake_case							) for row in solutions							)							)
     else:
          print("No solution exists!"							)
     return solved





def    __lowerCAmelCase   (    __snake_case       ,			__snake_case       ,			__snake_case       ,			__snake_case							):
     __lowerCAmelCase             =       len(__snake_case							)
     # Final check point.
     if i == j == (size - 1):
          __lowerCAmelCase             =       1
          return True

     __lowerCAmelCase             =       (not i < 0) and (not j < 0)  # Check lower bounds
     __lowerCAmelCase             =       (i < size) and (j < size)  # Check upper bounds

     if lower_flag and upper_flag:
          # check for already visited and block points.
          __lowerCAmelCase             =       (not solutions[i][j]) and (not maze[i][j])
          if block_flag:
               # check visited
               __lowerCAmelCase             =       1

               # check for directions
               if (
                   run_maze(__snake_case       ,			i + 1       ,			__snake_case       ,			__snake_case							)
                   or run_maze(__snake_case       ,			__snake_case       ,			j + 1       ,			__snake_case							)
                   or run_maze(__snake_case       ,			i - 1       ,			__snake_case       ,			__snake_case							)
                   or run_maze(__snake_case       ,			__snake_case       ,			j - 1       ,			__snake_case							)
               ):
                    return True

               __lowerCAmelCase             =       0
               return False
     return False


if __name__ == "__main__":
 import doctest

 doctest.testmod()






