



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'''
			_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=_UpperCAmelCase					)
			_UpperCAmelCase	 =     None

			while queue:
						((_UpperCAmelCase) ,  (_UpperCAmelCase))	 =     heappop(_UpperCAmelCase					)
						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(_UpperCAmelCase					)  # add the source manually
									path.reverse()
									return matrix[destination], path

						for i in range(len(_UpperCAmelCase					)					):
									_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(_UpperCAmelCase							,     (dist + 1, (nx, ny))					)
															_UpperCAmelCase	 =     dist + 1
															_UpperCAmelCase	 =     (x, y)

			return np.inf, []


if __name__ == "__main__":
							import doctest

							doctest.testmod()





from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_tf_available, is_torch_available


UpperCAmelCase__     = {
    "configuration_ctrl": ["CTRL_PRETRAINED_CONFIG_ARCHIVE_MAP", "CTRLConfig"],
    "tokenization_ctrl": ["CTRLTokenizer"],
}

try:
							if not is_torch_available():
														raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
							pass
else:
							UpperCAmelCase__     = [
							    "CTRL_PRETRAINED_MODEL_ARCHIVE_LIST",
							    "CTRLForSequenceClassification",
							    "CTRLLMHeadModel",
							    "CTRLModel",
							    "CTRLPreTrainedModel",
							]

try:
							if not is_tf_available():
														raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
							pass
else:
							UpperCAmelCase__     = [
							    "TF_CTRL_PRETRAINED_MODEL_ARCHIVE_LIST",
							    "TFCTRLForSequenceClassification",
							    "TFCTRLLMHeadModel",
							    "TFCTRLModel",
							    "TFCTRLPreTrainedModel",
							]


if TYPE_CHECKING:
							from .configuration_ctrl import CTRL_PRETRAINED_CONFIG_ARCHIVE_MAP, CTRLConfig
							from .tokenization_ctrl import CTRLTokenizer

							try:
														if not is_torch_available():
																					raise OptionalDependencyNotAvailable()
							except OptionalDependencyNotAvailable:
														pass
							else:
														from .modeling_ctrl import (
														    CTRL_PRETRAINED_MODEL_ARCHIVE_LIST,
														    CTRLForSequenceClassification,
														    CTRLLMHeadModel,
														    CTRLModel,
														    CTRLPreTrainedModel,
														)

							try:
														if not is_tf_available():
																					raise OptionalDependencyNotAvailable()
							except OptionalDependencyNotAvailable:
														pass
							else:
														from .modeling_tf_ctrl import (
														    TF_CTRL_PRETRAINED_MODEL_ARCHIVE_LIST,
														    TFCTRLForSequenceClassification,
														    TFCTRLLMHeadModel,
														    TFCTRLModel,
														    TFCTRLPreTrainedModel,
														)

else:
							import sys

							UpperCAmelCase__     = _LazyModule(__name__, globals()["__file__"], _import_structure, module_spec=__spec__)
