

"""simple docstring"""




from heapq import heappop, heappush

import numpy as np
def     UpperCAmelCase_       (						_A				,		_A				,		_A				,		_A				,		):





     '''simple docstring'''




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

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

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

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

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

     return np.inf, []


if __name__ == "__main__":
       import doctest

       doctest.testmod()





import doctest
from collections import deque

import numpy as np






class 	UpperCAmelCase__		:






  """simple docstring"""


  def __init__(							self						:		List[Any] )		->							None:
       SCREAMING_SNAKE_CASE__   =   [2, 1, 2, -1]
       SCREAMING_SNAKE_CASE__   =   [1, 2, 3, 4]







  def 				lowercase_		(							self						:		Optional[int] )		->							list[float]:
       SCREAMING_SNAKE_CASE__   =   len(self.first_signal )
       SCREAMING_SNAKE_CASE__   =   len(self.second_signal )

       SCREAMING_SNAKE_CASE__   =   max(__lowerCamelCase     ,       __lowerCamelCase )

       # create a zero matrix of max_length x max_length
       SCREAMING_SNAKE_CASE__   =   [[0] * max_length for i in range(__lowerCamelCase )]

       # fills the smaller signal with zeros to make both signals of same length
       if length_first_signal < length_second_signal:
            self.first_signal += [0] * (max_length - length_first_signal)
       elif length_first_signal > length_second_signal:
            self.second_signal += [0] * (max_length - length_second_signal)
       for i in range(__lowerCamelCase ):
            SCREAMING_SNAKE_CASE__   =   deque(self.second_signal )
            rotated_signal.rotate(__lowerCamelCase )
            for j, item in enumerate(__lowerCamelCase ):
                 matrix[i][j] += item

        # multiply the matrix with the first signal
       SCREAMING_SNAKE_CASE__   =   np.matmul(np.transpose(__lowerCamelCase )     ,       np.transpose(self.first_signal ) )

       # rounding-off to two decimal places
       return [round(__lowerCamelCase     ,       2 ) for i in final_signal]


if __name__ == "__main__":
       doctest.testmod()


