Minimum Moves to Spread Stones Over Grid
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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 theminimum number of moves required to place one stone in each cell.
Examples
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.
Solution
Method 1 – BFS with State Encoding
Intuition
Each cell must end up with exactly one stone. We encode the grid state and use BFS to explore all possible moves, always moving a stone from a cell with excess to a cell with deficit, and track the minimum moves.
Approach
- Encode the grid as a tuple of stone counts for each cell.
- Use BFS to explore all possible states, moving stones between adjacent cells.
- For each state, try moving a stone from any cell with more than one stone to any adjacent cell with less than one stone.
- Track visited states to avoid cycles.
- Stop when all cells have exactly one stone.
Code
C++
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
set<vector<vector<int>>> vis;
queue<pair<vector<vector<int>>, int>> q;
q.push({grid, 0});
vis.insert(grid);
while (!q.empty()) {
auto [g, moves] = q.front(); q.pop();
bool done = true;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
if (g[i][j] != 1) done = false;
if (done) return moves;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (g[i][j] > 1) {
for (auto [dx, dy] : vector<pair<int,int>>{{0,1},{0,-1},{1,0},{-1,0}}) {
int ni = i+dx, nj = j+dy;
if (ni>=0 && ni<3 && nj>=0 && nj<3 && g[ni][nj]<1) {
auto ng = g;
ng[i][j]--;
ng[ni][nj]++;
if (!vis.count(ng)) {
vis.insert(ng);
q.push({ng, moves+1});
}
}
}
}
}
}
}
return -1;
}
};
Go
func minimumMoves(grid [][]int) int {
type state struct{ g [3][3]int }
vis := map[[3][3]int]bool{}
q := []struct{ g [3][3]int; moves int }{{toArr(grid), 0}}
vis[toArr(grid)] = true
for len(q) > 0 {
s := q[0]; q = q[1:]
if isDone(s.g) { return s.moves }
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
if s.g[i][j] > 1 {
for _, d := range [][2]int{{0,1},{0,-1},{1,0},{-1,0}} {
ni, nj := i+d[0], j+d[1]
if ni>=0 && ni<3 && nj>=0 && nj<3 && s.g[ni][nj]<1 {
ng := s.g
ng[i][j]--
ng[ni][nj]++
if !vis[ng] {
vis[ng] = true
q = append(q, struct{ g [3][3]int; moves int }{ng, s.moves+1})
}
}
}
}
}
}
}
return -1
}
func toArr(grid [][]int) (a [3][3]int) { for i := range grid { for j := range grid[i] { a[i][j]=grid[i][j] } } ; return }
func isDone(g [3][3]int) bool { for i := 0; i < 3; i++ { for j := 0; j < 3; j++ { if g[i][j]!=1 { return false } } } ; return true }
Java
class Solution {
public int minimumMoves(int[][] grid) {
Set<String> vis = new HashSet<>();
Queue<int[][]> q = new LinkedList<>();
q.offer(copy(grid));
vis.add(encode(grid));
int moves = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int k = 0; k < size; ++k) {
int[][] g = q.poll();
if (done(g)) return moves;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (g[i][j] > 1) {
for (int[] d : new int[][]{{0,1},{0,-1},{1,0},{-1,0}}) {
int ni = i+d[0], nj = j+d[1];
if (ni>=0 && ni<3 && nj>=0 && nj<3 && g[ni][nj]<1) {
int[][] ng = copy(g);
ng[i][j]--;
ng[ni][nj]++;
String key = encode(ng);
if (!vis.contains(key)) {
vis.add(key);
q.offer(ng);
}
}
}
}
}
}
}
moves++;
}
return -1;
}
private boolean done(int[][] g) { for (int i=0;i<3;i++) for (int j=0;j<3;j++) if (g[i][j]!=1) return false; return true; }
private int[][] copy(int[][] g) { int[][] ng = new int[3][3]; for (int i=0;i<3;i++) for (int j=0;j<3;j++) ng[i][j]=g[i][j]; return ng; }
private String encode(int[][] g) { StringBuilder sb = new StringBuilder(); for (int i=0;i<3;i++) for (int j=0;j<3;j++) sb.append(g[i][j]); return sb.toString(); }
}
Kotlin
class Solution {
fun minimumMoves(grid: Array<IntArray>): Int {
val vis = mutableSetOf<String>()
val q = ArrayDeque<Pair<Array<IntArray>, Int>>()
q.add(grid.map { it.clone() }.toTypedArray() to 0)
vis.add(encode(grid))
while (q.isNotEmpty()) {
val (g, moves) = q.removeFirst()
if (done(g)) return moves
for (i in 0..2) {
for (j in 0..2) {
if (g[i][j] > 1) {
for ((dx, dy) in listOf(0 to 1, 0 to -1, 1 to 0, -1 to 0)) {
val ni = i+dx; val nj = j+dy
if (ni in 0..2 && nj in 0..2 && g[ni][nj]<1) {
val ng = g.map { it.clone() }.toTypedArray()
ng[i][j]--
ng[ni][nj]++
val key = encode(ng)
if (key !in vis) {
vis.add(key)
q.add(ng to moves+1)
}
}
}
}
}
}
}
return -1
}
private fun done(g: Array<IntArray>) = g.all { it.all { v -> v == 1 } }
private fun encode(g: Array<IntArray>) = g.joinToString("-") { it.joinToString(",") }
}
Python
class Solution:
def minimumMoves(self, grid: list[list[int]]) -> int:
from collections import deque
def encode(g: list[list[int]]) -> tuple:
return tuple(tuple(row) for row in g)
def done(g: list[list[int]]) -> bool:
return all(g[i][j]==1 for i in range(3) for j in range(3))
vis = set()
q = deque([(grid, 0)])
vis.add(encode(grid))
while q:
g, moves = q.popleft()
if done(g): return moves
for i in range(3):
for j in range(3):
if g[i][j] > 1:
for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
ni, nj = i+dx, j+dy
if 0<=ni<3 and 0<=nj<3 and g[ni][nj]<1:
ng = [row[:] for row in g]
ng[i][j] -= 1
ng[ni][nj] += 1
key = encode(ng)
if key not in vis:
vis.add(key)
q.append((ng, moves+1))
return -1
Rust
use std::collections::{HashSet, VecDeque};
impl Solution {
pub fn minimum_moves(grid: Vec<Vec<i32>>) -> i32 {
let mut vis = HashSet::new();
let mut q = VecDeque::new();
q.push_back((grid.clone(), 0));
vis.insert(grid.clone());
while let Some((g, moves)) = q.pop_front() {
if g.iter().all(|row| row.iter().all(|&v| v == 1)) { return moves; }
for i in 0..3 {
for j in 0..3 {
if g[i][j] > 1 {
for (dx, dy) in [(0,1),(0,-1),(1,0),(-1,0)] {
let ni = i as i32 + dx;
let nj = j as i32 + dy;
if ni>=0 && ni<3 && nj>=0 && nj<3 && g[ni as usize][nj as usize]<1 {
let mut ng = g.clone();
ng[i][j] -= 1;
ng[ni as usize][nj as usize] += 1;
if !vis.contains(&ng) {
vis.insert(ng.clone());
q.push_back((ng, moves+1));
}
}
}
}
}
}
}
-1
}
}
TypeScript
class Solution {
minimumMoves(grid: number[][]): number {
const encode = (g: number[][]) => g.map(row => row.join(",")).join("-");
const done = (g: number[][]) => g.every(row => row.every(v => v === 1));
const vis = new Set<string>();
const q: [number[][], number][] = [[grid.map(row => [...row]), 0]];
vis.add(encode(grid));
while (q.length) {
const [g, moves] = q.shift()!;
if (done(g)) return moves;
for (let i = 0; i < 3; ++i) {
for (let j = 0; j < 3; ++j) {
if (g[i][j] > 1) {
for (const [dx, dy] of [[0,1],[0,-1],[1,0],[-1,0]]) {
const ni = i+dx, nj = j+dy;
if (ni>=0 && ni<3 && nj>=0 && nj<3 && g[ni][nj]<1) {
const ng = g.map(row => [...row]);
ng[i][j]--;
ng[ni][nj]++;
const key = encode(ng);
if (!vis.has(key)) {
vis.add(key);
q.push([ng, moves+1]);
}
}
}
}
}
}
}
return -1;
}
}
Complexity
- ⏰ Time complexity:
O(9!), as the number of unique grid states is limited and BFS explores all possible states. - 🧺 Space complexity:
O(9!), for the visited set and BFS queue.