from heapq import heappop, heappush

import numpy as np





def 	__lowerCamelCase							(UpperCAmelCase__     :							np.ndarray      , UpperCAmelCase__     :							tuple[int, int]      , UpperCAmelCase__     :							tuple[int, int]      , UpperCAmelCase__     :							bool      , ):
					SCREAMING_SNAKE_CASE    			=       grid.shape
					SCREAMING_SNAKE_CASE    			=       [-1, 1, 0, 0]
					SCREAMING_SNAKE_CASE    			=       [0, 0, -1, 1]
					if allow_diagonal:
										dx += [-1, -1, 1, 1]
										dy += [-1, 1, -1, 1]

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

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

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

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

					return np.inf, []


if __name__ == "__main__":
					import doctest

					doctest.testmod()





from __future__ import annotations

from collections.abc import Iterator
from typing import Generic, TypeVar

_lowerCamelCase					:   Optional[Any]							=		TypeVar('''T''')


class 						lowercase    (     Generic[T]     ):




							def __init__(						self   :					Any	,							_UpperCamelCase   :					T      )					->				Any:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE    			=       data
												SCREAMING_SNAKE_CASE    			=       None





							def __str__(						self   :					Union[str, Any]      )					->				str:



												'''simple docstring'''

												return F"{self.data}"



class 						lowercase    (     Generic[T]     ):




							def __init__(						self   :					Optional[int]      )					->				None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE    			=       None




							def __iter__(						self   :					str      )					->				Iterator[T]:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE    			=       self.top
												while node:
																	yield node.data
																	SCREAMING_SNAKE_CASE    			=       node.next




							def __str__(						self   :					int      )					->				str:



												'''simple docstring'''

												return "->".join([str(_UpperCamelCase      ) for item in self]      )




							def __len__(						self   :					Tuple      )					->				int:



												'''simple docstring'''

												return len(tuple(iter(self      )      )      )




							def 	__snake_case(						self   :					Union[str, Any]      )					->				bool:



												'''simple docstring'''

												return self.top is None




							def 	__snake_case(						self   :					str	,							_UpperCamelCase   :					T      )					->				None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE    			=       Node(_UpperCamelCase      )
												if not self.is_empty():
																	SCREAMING_SNAKE_CASE    			=       self.top
												SCREAMING_SNAKE_CASE    			=       node




							def 	__snake_case(						self   :					Union[str, Any]      )					->				T:



												'''simple docstring'''

												if self.is_empty():
																	raise IndexError("pop from empty stack"      )
												assert isinstance(self.top	,							_UpperCamelCase      )
												SCREAMING_SNAKE_CASE    			=       self.top
												SCREAMING_SNAKE_CASE    			=       self.top.next
												return pop_node.data




							def 	__snake_case(						self   :					Union[str, Any]      )					->				T:



												'''simple docstring'''

												if self.is_empty():
																	raise IndexError("peek from empty stack"      )

												assert self.top is not None
												return self.top.data





							def 	__snake_case(						self   :					Dict      )					->				None:



												'''simple docstring'''

												SCREAMING_SNAKE_CASE    			=       None


if __name__ == "__main__":
							from doctest import testmod

							testmod()




