def     lowerCAmelCase_			(   _SCREAMING_SNAKE_CASE     :				list[list[int]]		, _SCREAMING_SNAKE_CASE     :				int		, _SCREAMING_SNAKE_CASE     :				int		, _SCREAMING_SNAKE_CASE     :				list[int]			):

						# 1. Validate that path exists between current and next vertices
						if graph[path[curr_ind - 1]][next_ver] == 0:
												return False

						# 2. Validate that next vertex is not already in path
						return not any(vertex == next_ver for vertex in path			)






def     lowerCAmelCase_			(   _SCREAMING_SNAKE_CASE     :				list[list[int]]		, _SCREAMING_SNAKE_CASE     :				list[int]		, _SCREAMING_SNAKE_CASE     :				int			):

						# Base Case
						if curr_ind == len(_SCREAMING_SNAKE_CASE			):
												# return whether path exists between current and starting vertices
												return graph[path[curr_ind - 1]][path[0]] == 1

						# Recursive Step
						for next_ver in range(0		, len(_SCREAMING_SNAKE_CASE			)			):
												if valid_connection(_SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE			):
																		# Insert current vertex  into path as next transition
																		UpperCamelCase_		:							List[Any]  =		next_ver
																		# Validate created path
																		if util_hamilton_cycle(_SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		, curr_ind + 1			):
																								return True
																		# Backtrack
																		UpperCamelCase_		:							str  =		-1
						return False







def     lowerCAmelCase_			(   _SCREAMING_SNAKE_CASE     :				list[list[int]]		, _SCREAMING_SNAKE_CASE     :				int = 0			):
						UpperCamelCase_		:							Dict  =		[-1] * (len(_SCREAMING_SNAKE_CASE			) + 1)
						# initialize start and end of path with starting index
						UpperCamelCase_		:							Tuple  =		start_index
						# evaluate and if we find answer return path either return empty array
						return path if util_hamilton_cycle(_SCREAMING_SNAKE_CASE		, _SCREAMING_SNAKE_CASE		, 1			) else []







from heapq import heappop, heappush

import numpy as np






def     lowerCAmelCase_			(   _SCREAMING_SNAKE_CASE     :				np.ndarray		, _SCREAMING_SNAKE_CASE     :				tuple[int, int]		, _SCREAMING_SNAKE_CASE     :				tuple[int, int]		, _SCREAMING_SNAKE_CASE     :				bool		, ):
						UpperCamelCase_,UpperCamelCase_		:							Union[str, Any]  =		grid.shape
						UpperCamelCase_		:							List[str]  =		[-1, 1, 0, 0]
						UpperCamelCase_		:							Dict  =		[0, 0, -1, 1]
						if allow_diagonal:
												dx += [-1, -1, 1, 1]
												dy += [-1, 1, -1, 1]

						UpperCamelCase_,UpperCamelCase_		:							List[Any]  =		[(0, source)], set()
						UpperCamelCase_		:							Any  =		np.full((rows, cols)		, np.inf			)
						UpperCamelCase_		:							List[str]  =		0
						UpperCamelCase_		:							Union[str, Any]  =		np.empty((rows, cols)		, dtype=_SCREAMING_SNAKE_CASE			)
						UpperCamelCase_		:							Optional[int]  =		None

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

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

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

						return np.inf, []


if __name__ == "__main__":
	import doctest

	doctest.testmod()






