



'''simple docstring'''




from heapq import heappop, heappush

import numpy as np


def        lowerCAmelCase_     (			_lowerCamelCase:     np.ndarray ,   _lowerCamelCase:     tuple[int, int] ,   _lowerCamelCase:     tuple[int, int] ,   _lowerCamelCase:     bool ,   ):
		__SCREAMING_SNAKE_CASE :	Optional[Any]					 =	grid.shape
		__SCREAMING_SNAKE_CASE :	str					 =	[-1, 1, 0, 0]
		__SCREAMING_SNAKE_CASE :	int					 =	[0, 0, -1, 1]
		if allow_diagonal:
				dx += [-1, -1, 1, 1]
				dy += [-1, 1, -1, 1]

		__SCREAMING_SNAKE_CASE :	Dict					 =	[(0, source)], set()
		__SCREAMING_SNAKE_CASE :	Optional[Any]					 =	np.full((rows, cols) ,   np.inf      )
		__SCREAMING_SNAKE_CASE :	Optional[Any]					 =	0
		__SCREAMING_SNAKE_CASE :	Optional[int]					 =	np.empty((rows, cols) ,   dtype=UpperCAmelCase__      )
		__SCREAMING_SNAKE_CASE :	Dict					 =	None

		while queue:
				(__SCREAMING_SNAKE_CASE) :	List[Any]					 =	heappop(UpperCAmelCase__      )
				if (x, y) in visited:
						continue
				visited.add((x, y)      )

				if (x, y) == destination:
						__SCREAMING_SNAKE_CASE :	Any					 =	[]
						while (x, y) != source:
								path.append((x, y)      )
								__SCREAMING_SNAKE_CASE :	int					 =	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 :	Union[str, Any]					 =	x + dx[i], y + dy[i]
						if 0 <= nx < rows and 0 <= ny < cols:
								__SCREAMING_SNAKE_CASE :	Optional[Any]					 =	grid[nx][ny]
								if next_node == 1 and matrix[nx, ny] > dist + 1:
										heappush(UpperCAmelCase__ ,   (dist + 1, (nx, ny))      )
										__SCREAMING_SNAKE_CASE :	Any					 =	dist + 1
										__SCREAMING_SNAKE_CASE :	Union[str, Any]					 =	(x, y)

		return np.inf, []


if __name__ == "__main__":
						import doctest

						doctest.testmod()




'''simple docstring'''




UpperCamelCase__ :			List[str]												=				'''0.21.0'''

from .accelerator import Accelerator
from .big_modeling import (
    cpu_offload,
    cpu_offload_with_hook,
    disk_offload,
    dispatch_model,
    init_empty_weights,
    init_on_device,
    load_checkpoint_and_dispatch,
)
from .data_loader import skip_first_batches
from .launchers import debug_launcher, notebook_launcher
from .state import PartialState
from .utils import (
    DeepSpeedPlugin,
    DistributedDataParallelKwargs,
    DistributedType,
    FullyShardedDataParallelPlugin,
    GradScalerKwargs,
    InitProcessGroupKwargs,
    find_executable_batch_size,
    infer_auto_device_map,
    is_rich_available,
    load_checkpoint_in_model,
    synchronize_rng_states,
)


if is_rich_available():
						from .utils import rich