Minimum Moves to Spread Stones Over Grid

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11



![](https://assets.leetcode.com/uploads/2023/08/23/example1-3.svg)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12



![](https://assets.leetcode.com/uploads/2023/08/23/example2-2.svg)

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 == 3
0 <= grid[i][j] <= 9
Sum of grid is equal to 9.

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

 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
29
30
31
32
33
34
35
36


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;
    }
};

 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
29
30
31


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 }

 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
29
30
31
32
33
34
35
36
37
38
39
40


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(); }
}

 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
29
30
31
32
33
34


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(",") }
}

 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


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

 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
29
30
31
32


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
    }
}

 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
29
30
31
32
33


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.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – BFS with State Encoding#

Intuition#

Approach#

Code#

Complexity#