'''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'''

import functools
from typing import Any


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


      if not isinstance(__lowerCamelCase ,		__lowerCamelCase				) or len(__lowerCamelCase				) == 0:
            raise ValueError("the string should be not empty string"				)

      if not isinstance(__lowerCamelCase ,		__lowerCamelCase				) or not all(
          isinstance(__lowerCamelCase ,		__lowerCamelCase				) and len(__lowerCamelCase				) > 0 for item in words				):
            raise ValueError("the words should be a list of non-empty strings"				)

      # Build trie
      lowercase_     =      {}
      lowercase_     =      "WORD_KEEPER"

      for word in words:
            lowercase_     =      trie
            for c in word:
                  if c not in trie_node:
                        lowercase_     =      {}

                  lowercase_     =      trie_node[c]

            lowercase_     =      True

      lowercase_     =      len(__lowerCamelCase				)

      # Dynamic programming method
      @functools.cache
      def is_breakable(__lowerCamelCase			:						int				) -> bool:
            if index == len_string:
                  return True

            lowercase_     =      trie
            for i in range(__lowerCamelCase ,		__lowerCamelCase				):
                  lowercase_     =      trie_node.get(string[i] ,		__lowerCamelCase				)

                  if trie_node is None:
                        return False

                  if trie_node.get(__lowerCamelCase ,		__lowerCamelCase				) and is_breakable(i + 1				):
                        return True

            return False

      return is_breakable(0				)


if __name__ == "__main__":
       import doctest

       doctest.testmod()






