2850. Minimum Moves to Spread Stones Over Grid


Problem Description

The problem presents a 3x3 matrix grid, where each cell of the grid contains a certain number of stones, with a total of 9 stones distributed across the matrix. Here, it's possible to have multiple stones in a single cell. The task is to move the stones such that there is exactly one stone in each cell. A move consists of transferring a stone from one cell to any adjacent cell (one that shares a side).

To solve this problem, we need to determine the minimum number of moves necessary to achieve the goal where each cell contains just one stone.

Intuition

Determining the minimum number of moves required to distribute the stones one per cell is akin to solving a puzzle where we move pieces on a board to reach an end configuration.

We recognize that each move can only transfer one stone to an adjacent cell. This move is effectively a displacement by a certain "distance". We can define this distance as the total number of vertical and horizontal steps required to move a stone from its initial position to the target cell.

One way to approach this problem is through bit masking and dynamic programming, which can manage the permutations of moves to ensure each stone ends in a unique cell.

Here's the intuition behind the solution:

  1. We need to pair each starting point with a unique endpoint; that is, each initial stone's location (where stones are more than one) with one of the empty cells.

  2. To optimize the process, we can use a bit mask to represent each stone's possible destination cell choices. This provides a means to calculate the minimum number of moves cal(a, b) which uses the Manhattan distance (the sum of the absolute differences of their Cartesian coordinates).

  3. By iterating through all possible distributions of stones to open cells, we keep track of the minimum number of moves required to reach each distribution from the starting point, using dynamic programming.

  4. The state f[i] in the dynamic array represents the minimum number of moves required to achieve the distribution encoded by the bitmask i.

  5. We iterate over all possible combinations of distributions of stones to empty cells ((1 << n) represents all combinations for n stones), calculating and updating the minimum number of moves for each combination.

In the given code, cal function calculates the Manhattan distance between a source and destination cell, left array holds the coordinates of empty cells, right array holds the coordinates of cells with more than one stone, and n is the number of empty cells. f is the dynamic programming array that holds the minimum moves required and bit_count is a method that counts the number of set bits (1 bits) in the binary representation of a number, which in this context, represents how many stones have been placed in their unique position so far.

The final answer is then the value of the last element in the dynamic programming array f, which represents the minimum number of moves required to reach the end configuration with unique stones.

Learn more about Breadth-First Search and Dynamic Programming patterns.

Solution Approach

To solve the minimum number of moves problem for distributing stones on a 3x3 grid, the Reference Solution Approach employs dynamic programming alongside bit masking to efficiently calculate the minimum moves required. Here's a walkthrough of how the implementation translates to an algorithm:

  1. Data Structures Used:

    • left list: Stores the coordinates of empty cells (cells that need stones).
    • right list: Stores the coordinates corresponding to the position of each stone that needs to move.
    • A dynamic array f indexed by bitmasks representing subsets of stones moved.
  2. Dynamic Programming (DP) State:

    • f[i]: Minimum number of moves needed to move k stones to the position dictated by the subset represented by the binary digits of i.
  3. Bit Masking:

    • Each bit in a bitmask represents whether a stone from the right list has been moved to the corresponding cell in the left list (an empty position).
    • The 1 << n operation is used to iterate over all possible subsets of stones, where n represents the number of stones needing to be moved.
    • i.bit_count() gives the number of stones that have already been moved according to bitmask i.
  4. Algorithm Steps:

    • Initialize the dynamic array f with infinity (inf) since initially, the number of moves required for each subset is unknown.
    • Set f[0] = 0 because no moves are required when no stones have been moved.
    • Iterate over all possible subsets of stone movements. For each subset i, iterate over all the positions j that could be the last move in the subset.
    • Update the dynamic programming state f[i] if moving a stone from position j in the right list to the position k-1 in the left list results in fewer moves. This is done using the Manhattan distance calculation cal(left[k - 1], right[j]).
  5. Function cal(a, b):

    • This function calculates the Manhattan distance between two points, a and b, which is the sum of the horizontal and vertical distances and is computed as |a[0] - b[0]| + |a[1] - b[1]|.
  6. DP Transition:

    • For each state i, we calculate the stone to be placed by counting the number of bits set in i (how many stones are already placed). We call this k.
    • Transition from every state i ^ (1 << j) (where i ^ (1 << j) means the state before placing the j-th stone) to state i, and the cost of this transition is the Manhattan distance between the stone's initial and target positions.
  7. Final Step:

    • The answer to the problem is in f[-1], which represents the minimum number of moves required after all stones are placed in their correct positions, taking into account all the permutations and combinations.

By implementing bit masking and intelligent dynamic programming using Manhattan distances, this approach effectively solves a potentially computationally expensive combinatorial problem in a more manageable and optimized way.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Example Walkthrough

Let's say we have a 3x3 grid with the following distribution of stones:

12 0 1
21 0 1
30 3 2

In the grid, 2, 1, 0, 3, etc., represent the number of stones in each cell. Empty cells are our target cells where we need to move stones. Let's apply the steps described in the Solution Approach to this grid:

  1. Data Structures Initialization:

    • left = [(0, 1), (1, 1), (2, 0)] - coordinates of empty cells.
    • right = [(0, 0), (2, 1), (2, 2), (0, 2), (1, 0)] - coordinates of cells with stones to move (each coordinate may repeat based on the number of stones).
    • f = [inf, inf, inf, ..., 0, inf, inf] - dynamic array initialized with infinity, except f[0].
  2. DP Initialization:

    • We start with f[0] = 0 because if no stones are moved, no moves are needed.
  3. Iterate over Subsets:

    • Now, we iterate over all combinations of moves. For example, when we consider a subset where only the first stone from the right list has been moved, the bitmask would be 00001 (assuming we have 5 stones to move).
  4. Calculating Moves:

    • Suppose we are checking the subset where we have moved the first and third stones, according to our example lists. The bitmask is 00101.
    • Now we want to place the fourth stone. We check the cost of moving it to all empty positions while considering the already moved stones.
  5. Distance Calculation with cal:

    • To update f[00101], we compute the Manhattan distances from the fourth stone's position (2, 2) to all possible empty positions. We estimate the cost for each possible move and keep the minimum.
  6. DP Transition:

    • We calculate the new state by setting the bit corresponding to the fourth stone, resulting in a new bitmask, say 01101.
    • We update f[01101] if the cost of moving the fourth stone added to f[00101] is less than the current value of f[01101].
  7. Repeat Steps:

    • We iterate the above steps, updating the DP array f until all stones are considered.
  8. Final Step:

    • After considering all subsets and moves, f[-1] (or f[(1 << n) - 1] if n is the total number of stones) will give us the minimum number of moves required to achieve our goal. For our example, if n = 5, then f[11111] represents the state where all 5 stones have been moved to empty cells.

This example walkthrough provides an illustration of how the solution approach works step-by-step to calculate the minimum number of moves needed to distribute stones on the 3x3 grid using bit masking and dynamic programming.

Solution Implementation

1class Solution:
2    def minimumMoves(self, grid: List[List[int]]) -> int:
3        # Calculates the Manhattan distance between point a and point b.
4        def calculate_distance(a: tuple, b: tuple) -> int:
5            return abs(a[0] - b[0]) + abs(a[1] - b[1])
6
7        empty_cells, filled_cells = [], []
8        # Iterate through the grid to separate empty cells and filled cells.
9        for i in range(3):
10            for j in range(3):
11                if grid[i][j] == 0:
12                    empty_cells.append((i, j))
13                else:
14                    # Add the filled cell multiple times (grid[i][j] - 1),
15                    # equal to the value in the cell minus 1.
16                    for _ in range(grid[i][j] - 1):
17                        filled_cells.append((i, j))
18
19        num_empty_cells = len(empty_cells)
20        # Initialize an array 'dp' to store the minimum distance for each subset of empty cells.
21        dp = [float('inf')] * (1 << num_empty_cells)
22        dp[0] = 0
23      
24        # Iterate over all subsets of empty cells.
25        for mask in range(1, 1 << num_empty_cells):
26            num_filled_cells = mask.bit_count()
27            for j in range(num_empty_cells):
28                if mask >> j & 1:
29                    # For each subset, calculate the minimum distance to move the
30                    # filled cell 'num_filled_cells - 1' to the position of the j-th empty cell.
31                    # Remove the j-th empty cell (1 << j) from the current subset (mask ^ (1 << j)).
32                    # min_distance is the minimum of the current value and the new calculated distance.
33                    dp[mask] = min(dp[mask], dp[mask ^ (1 << j)] + calculate_distance(empty_cells[num_filled_cells - 1], filled_cells[j]))
34      
35        # Return the last element in dp which represents the minimum distance
36        # for all empty cells filled.
37        return dp[-1]
38
1class Solution {
2    public int minimumMoves(int[][] grid) {
3        List<int[]> emptySpaces = new ArrayList<>();
4        List<int[]> obstacles = new ArrayList<>();
5      
6        // Identify empty spaces and obstacles
7        for (int row = 0; row < 3; ++row) {
8            for (int col = 0; col < 3; ++col) {
9                if (grid[row][col] == 0) {
10                    emptySpaces.add(new int[] {row, col});
11                } else {
12                    // If the cell is not empty, put obstacles according to the number specified in the cell
13                    for (int count = 1; count < grid[row][col]; ++count) {
14                        obstacles.add(new int[] {row, col});
15                    }
16                }
17            }
18        }
19
20        int numEmptySpaces = emptySpaces.size();
21        int[] dp = new int[1 << numEmptySpaces]; // Dynamic programming array to store minimum moves
22        Arrays.fill(dp, Integer.MAX_VALUE); // Initialize all moves to a large number
23        dp[0] = 0; // Zero moves needed when there's no empty space covered
24      
25        // Calculate minimum moves using bit masking to represent covering of each empty spaces.
26        for (int mask = 1; mask < (1 << numEmptySpaces); ++mask) {
27            int moves = Integer.bitCount(mask); // Count the number of covered empty spaces
28            for (int i = 0; i < numEmptySpaces; ++i) {
29                if ((mask >> i & 1) == 1) {
30                    // Update the DP table if a space gets covered
31                    dp[mask] = Math.min(dp[mask], dp[mask ^ (1 << i)] + calculateDistance(emptySpaces.get(moves - 1), obstacles.get(i)));
32                }
33            }
34        }
35      
36        // Return the minimum moves to cover all empty spaces
37        return dp[(1 << numEmptySpaces) - 1];
38    }
39
40    // Helper method to calculate Manhattan distance between two points on the grid
41    private int calculateDistance(int[] pointA, int[] pointB) {
42        return Math.abs(pointA[0] - pointB[0]) + Math.abs(pointA[1] - pointB[1]);
43    }
44}
45
1#include <vector>
2#include <cstring>
3#include <utility>
4#include <cmath>
5
6class Solution {
7public:
8    // This function aims to find the minimum moves needed to match pairs of points.
9    int minimumMoves(std::vector<std::vector<int>>& grid) {
10        // Define a pair of integers type for easier use
11        using Point = std::pair<int, int>;
12      
13        // Vectors to store the positions of empty spaces (left) and blocks (right)
14        std::vector<Point> emptySpaces, blockEnds;
15      
16        // Iterating over the grid to separate empty spaces and blocks
17        for (int i = 0; i < 3; ++i) {
18            for (int j = 0; j < 3; ++j) {
19                if (grid[i][j] == 0) {
20                    emptySpaces.emplace_back(i, j);
21                } else {
22                    for (int k = 1; k < grid[i][j]; ++k) {
23                        blockEnds.emplace_back(i, j);
24                    }
25                }
26            }
27        }
28      
29        // Lambda function to calculate the Manhattan distance between two points.
30        auto calculateDistance = [](Point a, Point b) {
31            return std::abs(a.first - b.first) + std::abs(a.second - b.second);
32        };
33      
34        int n = emptySpaces.size();
35      
36        // Dynamic programming table f to track the minimum moves to match pairs.
37        int dpTable[1 << n];
38        memset(dpTable, 0x3f, sizeof(dpTable)); // Initialize with a large number 
39        dpTable[0] = 0; // Base case: no moves needed when no empty spaces are matched
40      
41        // Iterate through each subset of empty spaces
42        for (int i = 1; i < 1 << n; ++i) {
43            int k = __builtin_popcount(i); // Number of selected empty spaces
44            for (int j = 0; j < n; ++j) {
45                // Check if the j-th empty space is included in the current subset
46                if (i >> j & 1) {
47                    // Calculate the minimum moves for the current subset
48                    dpTable[i] = std::min(dpTable[i], dpTable[i ^ (1 << j)] + calculateDistance(emptySpaces[k - 1], blockEnds[j]));
49                }
50            }
51        }
52      
53        // Return the minimum moves needed to match all pairs.
54        return dpTable[(1 << n) - 1];
55    }
56};
57
1// Function to compute the minimum moves required.
2function minimumMoves(grid: number[][]): number {
3    // Initialize arrays to store positions of zeros 'left' and non-zeros 'right'.
4    const zeroPositions: number[][] = [];
5    const nonzeroPositions: number[][] = [];
6
7    // Loop over the grid to fill the zeroPositions and nonzeroPositions arrays.
8    for (let row = 0; row < 3; ++row) {
9        for (let col = 0; col < 3; ++col) {
10            if (grid[row][col] === 0) {
11                zeroPositions.push([row, col]);
12            } else {
13                for (let count = 1; count < grid[row][col]; ++count) {
14                    nonzeroPositions.push([row, col]);
15                }
16            }
17        }
18    }
19
20    // Helper function to calculate the Manhattan distance between two points.
21    const calculateDistance = (pointA: number[], pointB: number[]) => {
22        return Math.abs(pointA[0] - pointB[0]) + Math.abs(pointA[1] - pointB[1]);
23    };
24
25    // The number of zeros in the grid.
26    const zeroCount = zeroPositions.length;
27
28    // Initialize the DP table with high values (much like infinity).
29    const dp: number[] = Array(1 << zeroCount).fill(1 << 30);
30
31    // Base case: no moves required when there are no zeros.
32    dp[0] = 0;
33
34    // Loop over all subsets of zeros.
35    for (let i = 0; i < 1 << zeroCount; ++i) {
36        let setBitsCount = 0;
37
38        // Count how many bits are set in the current subset.
39        for (let bit = 0; bit < zeroCount; ++bit) {
40            if ((i >> bit) & 1) {
41                ++setBitsCount;
42            }
43        }
44
45        // Try moving each zero to its corresponding non-zero position.
46        for (let pos = 0; pos < zeroCount; ++pos) {
47            if ((i >> pos) & 1) {
48                dp[i] = Math.min(dp[i], dp[i ^ (1 << pos)] + calculateDistance(zeroPositions[setBitsCount - 1], nonzeroPositions[pos]));
49            }
50        }
51    }
52
53    // Return the minimum moves required to assign each zero to a non-zero position.
54    return dp[(1 << zeroCount) - 1];
55}
56

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n * 2^n). The reason for this time complexity is due to the combination of iterating over all subsets of "left" and calculating the minimum distances against all elements in "right". Specifically:

  • There are n cities on the left side, resulting in 2^n subsets due to the binary representation used to enumerate these subsets.
  • For each subset (represented by i), we use bit_count() which contributes O(n) as it counts the number of set bits in the binary representation of the integer.
  • The inner loop runs n times for each subset to calculate distances and find the minimum after excluding elements using the XOR operation i ^ (1 << j).
  • Each call to cal() function is constant time, however, it's called n times in the worst case.

Hence, combining these factors, we end up with O(n * 2^n).

Space Complexity

The space complexity of the code is O(2^n). The reasons are as follows:

  • We maintain an array f of size 2^n that keeps track of the minimum distance for every subset of cities on the "left".
  • The left and right lists have a linear space complexity based on the input size, in the worst case it would be O(n), which is eclipsed by the space needed for f.
  • Auxiliary space used by the recursion stack for bit_count() or temporary variables in the loops are constant in comparison to the space used by f.

Overall, the dominant factor here is the f array, hence the space complexity is O(2^n).

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄