

def a_		(       UpperCamelCase_   :							int   ,					UpperCamelCase_   :							int   ,					UpperCamelCase_   :							int   ,					UpperCamelCase_   :							int  )							->   int:







 """simple docstring"""

 return len_board * len_board_column * row + column







def a_		(       UpperCamelCase_   :							list[list[str]]   ,					UpperCamelCase_   :							str   ,					UpperCamelCase_   :							int   ,					UpperCamelCase_   :							int   ,					UpperCamelCase_   :							int   ,					UpperCamelCase_   :							set[int]   ,					)							->   bool:







 """simple docstring"""

 if board[row][column] != word[word_index]:
  return False

 if word_index == len(UpperCamelCase_  ) - 1:
  return True

 lowerCamelCase      						=    [(0, 1), (0, -1), (-1, 0), (1, 0)]
 lowerCamelCase      						=    len(UpperCamelCase_  )
 lowerCamelCase      						=    len(board[0]  )
 for direction in traverts_directions:
  lowerCamelCase      						=    row + direction[0]
  lowerCamelCase      						=    column + direction[1]
  if not (0 <= next_i < len_board and 0 <= next_j < len_board_column):
   continue

  lowerCamelCase      						=    get_point_key(UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_  )
  if key in visited_points_set:
   continue

  visited_points_set.add(UpperCamelCase_  )
  if exits_word(UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_   ,					word_index + 1   ,					UpperCamelCase_  ):
   return True

  visited_points_set.remove(UpperCamelCase_  )

 return False







def a_		(       UpperCamelCase_   :							list[list[str]]   ,					UpperCamelCase_   :							str  )							->   bool:







 """simple docstring"""

 lowerCamelCase      						=    (
     'The board should be a non empty matrix of single chars strings.'
 )

 lowerCamelCase      						=    len(UpperCamelCase_  )
 if not isinstance(UpperCamelCase_   ,					UpperCamelCase_  ) or len(UpperCamelCase_  ) == 0:
  raise ValueError(UpperCamelCase_  )

 for row in board:
  if not isinstance(UpperCamelCase_   ,					UpperCamelCase_  ) or len(UpperCamelCase_  ) == 0:
   raise ValueError(UpperCamelCase_  )

  for item in row:
   if not isinstance(UpperCamelCase_   ,					UpperCamelCase_  ) or len(UpperCamelCase_  ) != 1:
    raise ValueError(UpperCamelCase_  )

    # Validate word
 if not isinstance(UpperCamelCase_   ,					UpperCamelCase_  ) or len(UpperCamelCase_  ) == 0:
  raise ValueError(
      'The word parameter should be a string of length greater than 0.'  )

 lowerCamelCase      						=    len(board[0]  )
 for i in range(UpperCamelCase_  ):
  for j in range(UpperCamelCase_  ):
   if exits_word(
       UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_   ,					0   ,					{get_point_key(UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_   ,					UpperCamelCase_  )}  ):
    return True

 return False


if __name__ == "__main__":
     import doctest

     doctest.testmod()







from __future__ import annotations


class     lowerCAmelCase				:


       '''simple docstring'''







       def __init__(	self					:  Dict						,	__snake_case					:  int     )   -> None:







        '''simple docstring'''

        lowerCamelCase      						=    vertices
        lowerCamelCase      						=    [[0] * vertices for _ in range(__snake_case     )]

       def   lowerCamelCase__						(	self					:  List[str]						,	__snake_case					:  list[int]     )   -> None:







        '''simple docstring'''

        print('Vertex \t Distance from Source'     )
        for vertex in range(self.vertices     ):
         print(__snake_case						,	'\t\t'						,	distances_from_source[vertex]     )

       def   lowerCamelCase__						(	self					:  Optional[int]						,	__snake_case					:  list[int]						,	__snake_case					:  list[bool]     )   -> int:







        '''simple docstring'''

        lowerCamelCase      						=    1e7
        lowerCamelCase      						=    0

        # Search not nearest vertex not in the shortest path tree
        for vertex in range(self.vertices     ):
         if distances_from_source[vertex] < minimum and visited[vertex] is False:
          lowerCamelCase      						=    distances_from_source[vertex]
          lowerCamelCase      						=    vertex
        return min_index





       def   lowerCamelCase__						(	self					:  Optional[Any]						,	__snake_case					:  int     )   -> None:







        '''simple docstring'''

        lowerCamelCase      						=    [int(1e7     )] * self.vertices  # distances from the source
        lowerCamelCase      						=    0
        lowerCamelCase      						=    [False] * self.vertices

        for _ in range(self.vertices     ):
         lowerCamelCase      						=    self.minimum_distance(__snake_case						,	__snake_case     )
         lowerCamelCase      						=    True

         # Update dist value of the adjacent vertices
         # of the picked vertex only if the current
         # distance is greater than new distance and
         # the vertex in not in the shortest path tree
         for v in range(self.vertices     ):
          if (
              self.graph[u][v] > 0
              and visited[v] is False
              and distances[v] > distances[u] + self.graph[u][v]
          ):
           lowerCamelCase      						=    distances[u] + self.graph[u][v]

        self.print_solution(__snake_case     )


if __name__ == "__main__":
     _lowerCAmelCase :	Dict     				=    Graph(9)
     _lowerCAmelCase :	int     				=    [
         [0, 4, 0, 0, 0, 0, 0, 8, 0],
         [4, 0, 8, 0, 0, 0, 0, 1_1, 0],
         [0, 8, 0, 7, 0, 4, 0, 0, 2],
         [0, 0, 7, 0, 9, 1_4, 0, 0, 0],
         [0, 0, 0, 9, 0, 1_0, 0, 0, 0],
         [0, 0, 4, 1_4, 1_0, 0, 2, 0, 0],
         [0, 0, 0, 0, 0, 2, 0, 1, 6],
         [8, 1_1, 0, 0, 0, 0, 1, 0, 7],
         [0, 0, 2, 0, 0, 0, 6, 7, 0],
     ]
     graph.dijkstra(0)




