Welcome to Subscribe On Youtube
2850. Minimum Moves to Spread Stones Over Grid
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 == 30 <= grid[i][j] <= 9- Sum of
gridis equal to9.
Solutions
Solution 1: Naive BFS
The problem is essentially finding the shortest path from the initial state to the target state in a state graph, so we can use BFS to solve it. The initial state is grid, and the target state is [[1, 1, 1], [1, 1, 1], [1, 1, 1]]. In each operation, we can move a stone greater than $1$ from a cell to an adjacent cell that does not exceed $1$. If the target state is found, we can return the current layer number, which is the minimum number of moves.
Solution 2: State Compression Dynamic Programming
We can put all the coordinates $(i, j)$ of cells with a value of $0$ into an array $left$. If the value $v$ of a cell is greater than $1$, we put $v-1$ coordinates $(i, j)$ into an array $right$. The problem then becomes that each coordinate $(i, j)$ in $right$ needs to be moved to a coordinate $(x, y)$ in $left$, and we need to find the minimum number of moves.
Let’s denote the length of $left$ as $n$. We can use an $n$-bit binary number to represent whether each coordinate in $left$ is filled by a coordinate in $right$, where $1$ represents being filled, and $0$ represents not being filled. Initially, $f[i] = \infty$, and the rest $f[0]=0$.
Consider $f[i]$, let the number of $1$s in the binary representation of $i$ be $k$. We enumerate $j$ in the range $[0..n)$, if the $j$th bit of $i$ is $1$, then $f[i]$ can be transferred from $f[i \oplus (1 « j)]$, and the cost of the transfer is $cal(left[k-1], right[j])$, where $cal$ represents the Manhattan distance between two coordinates. The final answer is $f[(1 « n) - 1]$.
The time complexity is $O(n \times 2^n)$, and the space complexity is $O(2^n)$. Here, $n$ is the length of $left$, and in this problem, $n \le 9$.
-
class Solution { public int minimumMoves(int[][] grid) { Deque<String> q = new ArrayDeque<>(); q.add(f(grid)); Set<String> vis = new HashSet<>(); vis.add(f(grid)); int[] dirs = {-1, 0, 1, 0, -1}; for (int ans = 0;; ++ans) { for (int k = q.size(); k > 0; --k) { String p = q.poll(); if ("111111111".equals(p)) { return ans; } int[][] cur = g(p); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { if (cur[i][j] > 1) { for (int d = 0; d < 4; ++d) { int x = i + dirs[d]; int y = j + dirs[d + 1]; if (x >= 0 && x < 3 && y >= 0 && y < 3 && cur[x][y] < 2) { int[][] nxt = new int[3][3]; for (int r = 0; r < 3; ++r) { for (int c = 0; c < 3; ++c) { nxt[r][c] = cur[r][c]; } } nxt[i][j]--; nxt[x][y]++; String s = f(nxt); if (!vis.contains(s)) { vis.add(s); q.add(s); } } } } } } } } } private String f(int[][] grid) { StringBuilder sb = new StringBuilder(); for (int[] row : grid) { for (int x : row) { sb.append(x); } } return sb.toString(); } private int[][] g(String s) { int[][] grid = new int[3][3]; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { grid[i][j] = s.charAt(i * 3 + j) - '0'; } } return grid; } } -
class Solution { public: int minimumMoves(vector<vector<int>>& grid) { using pii = pair<int, int>; vector<pii> left, right; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { if (grid[i][j] == 0) { left.emplace_back(i, j); } else { for (int k = 1; k < grid[i][j]; ++k) { right.emplace_back(i, j); } } } } auto cal = [](pii a, pii b) { return abs(a.first - b.first) + abs(a.second - b.second); }; int n = left.size(); int f[1 << n]; memset(f, 0x3f, sizeof(f)); f[0] = 0; for (int i = 1; i < 1 << n; ++i) { int k = __builtin_popcount(i); for (int j = 0; j < n; ++j) { if (i >> j & 1) { f[i] = min(f[i], f[i ^ (1 << j)] + cal(left[k - 1], right[j])); } } } return f[(1 << n) - 1]; } }; -
class Solution: def minimumMoves(self, grid: List[List[int]]) -> int: q = deque([tuple(tuple(row) for row in grid)]) vis = set(q) ans = 0 dirs = (-1, 0, 1, 0, -1) while 1: for _ in range(len(q)): cur = q.popleft() if all(x for row in cur for x in row): return ans for i in range(3): for j in range(3): if cur[i][j] > 1: for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < 3 and 0 <= y < 3 and cur[x][y] < 2: nxt = [list(row) for row in cur] nxt[i][j] -= 1 nxt[x][y] += 1 nxt = tuple(tuple(row) for row in nxt) if nxt not in vis: vis.add(nxt) q.append(nxt) ans += 1 -
func minimumMoves(grid [][]int) int { left := [][2]int{} right := [][2]int{} for i := 0; i < 3; i++ { for j := 0; j < 3; j++ { if grid[i][j] == 0 { left = append(left, [2]int{i, j}) } else { for k := 1; k < grid[i][j]; k++ { right = append(right, [2]int{i, j}) } } } } cal := func(a, b [2]int) int { return abs(a[0]-b[0]) + abs(a[1]-b[1]) } n := len(left) f := make([]int, 1<<n) f[0] = 0 for i := 1; i < 1<<n; i++ { f[i] = 1 << 30 k := bits.OnesCount(uint(i)) for j := 0; j < n; j++ { if i>>j&1 == 1 { f[i] = min(f[i], f[i^(1<<j)]+cal(left[k-1], right[j])) } } } return f[(1<<n)-1] } func abs(x int) int { if x < 0 { return -x } return x } -
function minimumMoves(grid: number[][]): number { const left: number[][] = []; const right: number[][] = []; for (let i = 0; i < 3; ++i) { for (let j = 0; j < 3; ++j) { if (grid[i][j] === 0) { left.push([i, j]); } else { for (let k = 1; k < grid[i][j]; ++k) { right.push([i, j]); } } } } const cal = (a: number[], b: number[]) => { return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]); }; const n = left.length; const f: number[] = Array(1 << n).fill(1 << 30); f[0] = 0; for (let i = 0; i < 1 << n; ++i) { let k = 0; for (let j = 0; j < n; ++j) { if ((i >> j) & 1) { ++k; } } for (let j = 0; j < n; ++j) { if ((i >> j) & 1) { f[i] = Math.min(f[i], f[i ^ (1 << j)] + cal(left[k - 1], right[j])); } } } return f[(1 << n) - 1]; }