






from heapq import heappop, heappush

import numpy as np


def        _a  (     UpperCamelCase_					:				np.ndarray    ,   UpperCamelCase_					:				tuple[int, int]    ,   UpperCamelCase_					:				tuple[int, int]    ,   UpperCamelCase_					:				bool    ,   ) ->   tuple[float | int, list[tuple[int, int]]]:
						"""simple docstring"""







						lowerCAmelCase__      ,							lowerCAmelCase__       =						grid.shape
						lowerCAmelCase__       =						[-1, 1, 0, 0]
						lowerCAmelCase__       =						[0, 0, -1, 1]
						if allow_diagonal:
												dx += [-1, -1, 1, 1]
												dy += [-1, 1, -1, 1]

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

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

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

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

						return np.inf, []


if __name__ == "__main__":
	import doctest

	doctest.testmod()














def        _a  (     UpperCamelCase_					:				list    ,   UpperCamelCase_					:				list   ) ->   float:
						"""simple docstring"""







						_validate_point(UpperCamelCase_   )
						_validate_point(UpperCamelCase_   )
						if len(UpperCamelCase_   ) != len(UpperCamelCase_   ):
												raise ValueError("Both points must be in the same n-dimensional space"   )

						return float(sum(abs(a - b   ) for a, b in zip(UpperCamelCase_    ,   UpperCamelCase_   )   )   )


def        _a  (     UpperCamelCase_					:				list[float]   ) ->   None:
						"""simple docstring"""







						if point:
												if isinstance(UpperCamelCase_    ,   UpperCamelCase_   ):
																		for item in point:
																								if not isinstance(UpperCamelCase_    ,   (int, float)   ):
																														lowerCAmelCase__       =						(
																														    "Expected a list of numbers as input, found "
																														    F"{type(UpperCamelCase_   ).__name__}"
																														)
																														raise TypeError(UpperCamelCase_   )
												else:
																		lowerCAmelCase__       =						F"Expected a list of numbers as input, found {type(UpperCamelCase_   ).__name__}"
																		raise TypeError(UpperCamelCase_   )
						else:
												raise ValueError("Missing an input"   )


def        _a  (     UpperCamelCase_					:				list    ,   UpperCamelCase_					:				list   ) ->   float:
						"""simple docstring"""







						_validate_point(UpperCamelCase_   )
						_validate_point(UpperCamelCase_   )
						if len(UpperCamelCase_   ) != len(UpperCamelCase_   ):
												raise ValueError("Both points must be in the same n-dimensional space"   )

						return float(sum(abs(x - y   ) for x, y in zip(UpperCamelCase_    ,   UpperCamelCase_   )   )   )


if __name__ == "__main__":
	import doctest

	doctest.testmod()






