'''simple docstring'''

from heapq import heappop, heappush

import numpy as np


def __a (	__lowerCamelCase			:						np.ndarray ,		__lowerCamelCase			:						tuple[int, int] ,		__lowerCamelCase			:						tuple[int, int] ,		__lowerCamelCase			:						bool ,		)	->							tuple[float | int, list[tuple[int, int]]]:
      '''simple docstring'''


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

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

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

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

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

      return np.inf, []


if __name__ == "__main__":
       import doctest

       doctest.testmod()







'''simple docstring'''

def __a (	__lowerCamelCase			:						list[int] ,		__lowerCamelCase			:						int				)	->							bool:
      '''simple docstring'''


      lowercase_     =      len(__lowerCamelCase				)
      lowercase_     =      [[False] * (required_sum + 1) for _ in range(arr_len + 1				)]

      # for each arr value, a sum of zero(0) can be formed by not taking any element
      # hence True/1
      for i in range(arr_len + 1				):
            lowercase_     =      True

      # sum is not zero and set is empty then false
      for i in range(1 ,		required_sum + 1				):
            lowercase_     =      False

      for i in range(1 ,		arr_len + 1				):
            for j in range(1 ,		required_sum + 1				):
                  if arr[i - 1] > j:
                        lowercase_     =      subset[i - 1][j]
                  if arr[i - 1] <= j:
                        lowercase_     =      subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]

      return subset[arr_len][required_sum]


if __name__ == "__main__":
       import doctest

       doctest.testmod()






