
from __future__ import annotations






def      lowerCamelCase__       (       __lowerCAmelCase						:						list[list[int]]       ):




			"""simple docstring"""


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






def      lowerCamelCase__       (       __lowerCAmelCase						:						list[list[int]]					,							__lowerCAmelCase						:						int					,							__lowerCAmelCase						:						int					,							__lowerCAmelCase						:						list[list[int]]       ):




			"""simple docstring"""


			lowerCAmelCase_      			=			len(__lowerCAmelCase       )
			# 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(__lowerCAmelCase					,							i + 1					,							__lowerCAmelCase					,							__lowerCAmelCase       )
									    or run_maze(__lowerCAmelCase					,							__lowerCAmelCase					,							j + 1					,							__lowerCAmelCase       )
									    or run_maze(__lowerCAmelCase					,							i - 1					,							__lowerCAmelCase					,							__lowerCAmelCase       )
									    or run_maze(__lowerCAmelCase					,							__lowerCAmelCase					,							j - 1					,							__lowerCAmelCase       )
									):
												return True

									lowerCAmelCase_      			=			0
									return False
			return False


if __name__ == "__main__":
					import doctest

					doctest.testmod()





import math





class 			_lowerCAmelCase      :




				def __init__(      self       ,       _UpperCamelCase=0  )       ->   Tuple:  # a graph with Node 0,1,...,N-1
							lowerCAmelCase_      			=			n
							lowerCAmelCase_      			=			[
							    [math.inf for j in range(0       ,       _UpperCamelCase  )] for i in range(0       ,       _UpperCamelCase  )
							]  # adjacency matrix for weight
							lowerCAmelCase_      			=			[
							    [math.inf for j in range(0       ,       _UpperCamelCase  )] for i in range(0       ,       _UpperCamelCase  )
							]  # dp[i][j] stores minimum distance from i to j




				def   __a		(      self       ,       _UpperCamelCase       ,       _UpperCamelCase       ,       _UpperCamelCase  )       ->   List[Any]:
							lowerCAmelCase_      			=			w




				def   __a		(      self  )       ->   List[str]:
							for k in range(0       ,       self.n  ):
										for i in range(0       ,       self.n  ):
													for j in range(0       ,       self.n  ):
																lowerCAmelCase_      			=			min(self.dp[i][j]       ,       self.dp[i][k] + self.dp[k][j]  )




				def   __a		(      self       ,       _UpperCamelCase       ,       _UpperCamelCase  )       ->   Dict:
							return self.dp[u][v]


if __name__ == "__main__":
			_A     =  Graph(5)
			graph.add_edge(0, 2, 9)
			graph.add_edge(0, 4, 10)
			graph.add_edge(1, 3, 5)
			graph.add_edge(2, 3, 7)
			graph.add_edge(3, 0, 10)
			graph.add_edge(3, 1, 2)
			graph.add_edge(3, 2, 1)
			graph.add_edge(3, 4, 6)
			graph.add_edge(4, 1, 3)
			graph.add_edge(4, 2, 4)
			graph.add_edge(4, 3, 9)
			graph.floyd_warshall()
			graph.show_min(1, 4)
			graph.show_min(0, 3)



