We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Moves to Spread Stones Over Grid

Number: 3092

Difficulty: Medium

Paid? No

Companies: Microsoft, TikTok, Apple

Problem Description

You are given a 3 x 3 grid that contains exactly 9 stones in total (with possibly multiple stones per cell). In one move you can take a single stone and move it to an adjacent cell (cells sharing a side). The goal is to have exactly one stone in every cell. Return the minimum number of moves required to achieve this.

Key Insights

  • Each cell’s “imbalance” can be computed by subtracting 1 from its stone count.
  • Cells with a surplus (value > 0) will act as donors while cells with a deficit (value < 0) will be recipients.
  • Because the grid is small, we can list each donor stone (repeating coordinates according to the surplus) and each deficit cell (repeating coordinates according to the shortage) and then solve an assignment problem.
  • The cost to move a stone from one cell to another is the Manhattan distance between the coordinates.
  • We can solve the assignment problem using a dynamic programming solution with bitmasking to assign donor stones to deficit spots optimally.

Space and Time Complexity

Time Complexity: O(n * 2^n) where n is the total number of stones that need to be moved (at most 9 in the worst case), which is effectively constant. Space Complexity: O(2^n) for the DP array.

Solution

We first calculate the imbalance for every cell, where imbalance = grid[r][c] - 1. For cells with imbalance > 0, we create a list of donor locations repeated by the surplus amount. For cells with imbalance < 0, we create a list of deficit locations repeated by the absolute value of the deficit.

Next, we precompute the Manhattan distance cost between every donor and every deficit. Then, we solve the assignment problem using a bitmask dynamic programming (DP) approach, where the DP state represents which deficit positions have already been paired with donor stones. At each step, we assign the next unassigned donor to any remaining deficit and update the cost accordingly. Finally, the minimum cost in the DP table yields the fewest moves needed.

Code Solutions

# Python solution using DP with bitmasking

def minMoves(grid):
    # List donors (cells with surplus stones) and deficits (cells with missing stones)
    donors = []  # each element is (row, col)
    deficits = []  # each element is (row, col)
    
    for r in range(3):
        for c in range(3):
            excess = grid[r][c] - 1
            if excess > 0:
                for _ in range(excess):
                    donors.append((r, c))
            elif excess < 0:
                for _ in range(-excess):
                    deficits.append((r, c))
    
    # Number of stones to reassign (donors and deficits are equal in count)
    n = len(donors)
    # Precompute Manhattan distances from each donor to each deficit
    cost = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            cost[i][j] = abs(donors[i][0] - deficits[j][0]) + abs(donors[i][1] - deficits[j][1])
    
    # dp[mask] represents the minimum cost to assign stones for deficits indicated by mask
    # mask bits: if j-th bit is set then the j-th deficit has been assigned
    dp = [float('inf')] * (1 << n)
    dp[0] = 0
    
    for mask in range(1 << n):
        # Count donors already assigned as next donor index
        donor_index = bin(mask).count("1")
        if donor_index >= n:
            continue
        # Try to assign donor_index to any unassigned deficit j
        for j in range(n):
            if not mask & (1 << j):
                new_mask = mask | (1 << j)
                dp[new_mask] = min(dp[new_mask], dp[mask] + cost[donor_index][j])
    
    return dp[(1 << n) - 1]

# Example usage:
grid1 = [[1,1,0],[1,1,1],[1,2,1]]
print(minMoves(grid1))  # Expected output: 3

grid2 = [[1,3,0],[1,0,0],[1,0,3]]
print(minMoves(grid2))  # Expected output: 4
← Back to All Questions