Leetcode # 2850. Minimum Moves to Spread Stones Over Grid

Problem

https://leetcode.com/contest/weekly-contest-362/problems/minimum-moves-to-spread-stones-over-grid/

Solution

z := len([True for row in grid for num in row if num == 0])

Time Complexity: O(z!)
Space Complexity: O(z!)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minimumMoves(self, grid: List[List[int]]) -> int:
    queue = deque()
    holes, stones = [], []
    for i in range(3):
      for j in range(3):
        if grid[i][j] == 0:
          holes.append((i, j))
        elif grid[i][j] > 1:
          stones += [(i, j)] * (grid[i][j] - 1)
          
    global manhattan
    manhattan = lambda a, b: abs(a[0] - b[0]) + abs(a[1] - b[1])
          
    @lru_cache(maxsize=factorial(len(stones)))
    def min_moves(holes, stones):
      if len(holes) == 0: return 0
      moves = inf
      for i, stone in enumerate(stones):
        moves = min(moves, 
                    manhattan(holes[0], stone) + min_moves(tuple(holes[1:]), tuple(stones[:i] + stones[i + 1:])))
      return moves
                    
    return min_moves(tuple(holes), tuple(stones))

#Factorial

Last Updated on 2023/09/10 by A1go