Skip to content

Minimum Moves to Spread Stones Over Grid⚓︎

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
2
3
4
5
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
2
3
4
5
6
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⚓︎

See reference (Chinese) and next_permutation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int, int>> from, to;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j]) {
                    for (int k = 1; k < grid[i][j]; k++) {
                        from.emplace_back(i, j);
                    }
                } else {
                    to.emplace_back(i, j);
                }
            }
        }

        int res = INT_MAX;
        do {
            int total = 0;
            for (int i = 0; i < from.size(); i++) {
                total += abs(from[i].first - to[i].first) + abs(from[i].second - to[i].second);
            }
            res = min(res, total);
        } while (next_permutation(from.begin(), from.end()));

        return res;
    }
};
  • Time complexity: \(O(8\times 8!)\);
  • Space complexity: \(O(3\times 3)\).