unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 2850: Minimum Moves to Spread Stones Over Grid

link

The problem restricts placing one stone per move, otherwise it would have been harder.

The problem here is to find the minimum total cost of assigning every empty cell to one extra stone. The cost of one such assignment is the Manhattan distance between the empty cell and the stone’s cell.

We construct a list of empty cells and a list of extra stones; these two lists must have same length. For each empty cell, we try placing one available extra stone. To be able to keep track of already assigned stones, we need each stone to be unique. More than one (extra) stones can come from the same cell. So, we use an extra coordinate for a stone to differentiate this case.

If there are n empty cells, the recursion tree has depth n. Width reduces by 1 at each level. So, time: \mathcal{O}(n!), space: \mathcal{O}(n).

from itertools import product as cartesian

class Solution:
    def min_cost_to_distribute(self, empty_cells, empty_index, extra_stones, assigned_stones, total_cost) -> int:
        if empty_index >= len(empty_cells):
            return total_cost
        
        min_cost = float('inf')
        for stone in extra_stones:
            if stone in assigned_stones:
                continue

            assigned_stones.add(stone)

            empty_cell = empty_cells[empty_index]
            current_cost = abs( empty_cell[0]-stone[0] ) + abs( empty_cell[1]-stone[1] )
            min_cost = min( min_cost, self.min_cost_to_distribute(empty_cells, empty_index+1, extra_stones, assigned_stones, total_cost+current_cost) )

            assigned_stones.remove(stone)
        
        return min_cost


    def minimumMoves(self, grid: List[List[int]]) -> int:
        n = len(grid)
        empty_cells, extra_stones = [], []
        for row, col in cartesian( list(range(n)), repeat=2 ):
            if grid[row][col] == 1:
                continue
            
            if grid[row][col] == 0:
                empty_cells.append((row, col))
            else:
                num_extras = grid[row][col]-1
                extra_stones.extend( [ (row, col, i) for i in range(num_extras) ] )
        
        if not empty_cells:
            return 0

        return self.min_cost_to_distribute(empty_cells, 0, extra_stones, set(), 0)

tanvirdotzaman

Leave a comment