2850. Minimum Moves to Spread Stones Over Grid

Problem Link

Description

---

You are given a 0-indexed 2D integer matrix grid of size 3 * 3, representing the number of stones in each cell. The grid contains exactly 9 stones, and there can be multiple stones in a single cell.

In one move, you can move a single stone from its current cell to any other cell if the two cells share a side.

Return the minimum number of moves required to place one stone in each cell.

 

Example 1:

Input: grid = [[1,1,0],[1,1,1],[1,2,1]]
Output: 3
Explanation: One possible sequence of moves to place one stone in each cell is: 
1- Move one stone from cell (2,1) to cell (2,2).
2- Move one stone from cell (2,2) to cell (1,2).
3- Move one stone from cell (1,2) to cell (0,2).
In total, it takes 3 moves to place one stone in each cell of the grid.
It can be shown that 3 is the minimum number of moves required to place one stone in each cell.

Example 2:

Input: grid = [[1,3,0],[1,0,0],[1,0,3]]
Output: 4
Explanation: One possible sequence of moves to place one stone in each cell is:
1- Move one stone from cell (0,1) to cell (0,2).
2- Move one stone from cell (0,1) to cell (1,1).
3- Move one stone from cell (2,2) to cell (1,2).
4- Move one stone from cell (2,2) to cell (2,1).
In total, it takes 4 moves to place one stone in each cell of the grid.
It can be shown that 4 is the minimum number of moves required to place one stone in each cell.

 

Constraints:

• grid.length == grid[i].length == 3
• 0 <= grid[i][j] <= 9
• Sum of grid is equal to 9.

Solution

---

Python3

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        zeroes = []
        A = []
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] > 0:
                    if grid[i][j] > 1:
                        A.append((i, j))
                elif grid[i][j] == 0:
                    zeroes.append((i, j))
        
        
        M, N = len(zeroes), len(A)
 
        def backtrack(index):
            if index == M: return 0
            
            x, y = zeroes[index]
            res = inf
            
            for j in range(N):
                dx, dy = A[j]
                if grid[dx][dy] == 1: continue
                    
                grid[dx][dy] -= 1
                distance = abs(x - dx) + abs(y - dy)
                
                res = min(res, distance + backtrack(index + 1))
                
                grid[dx][dy] += 1
            
            return res
                                 
        return backtrack(0)