Algorithms
Medium
2850
3092
Minimum Moves to Spread Stones Over Grid
minimum-moves-to-spread-stones-over-grid
"""
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:

[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:

[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.
"""
class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        
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:

[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:

[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.


Please complete the code below to solve above prblem:
```python
class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        
```

my_solution = Solution()

test_input = { "grid": [[1,1,0],[1,1,1],[1,2,1]] }
assert my_solution.minimumMoves(**test_input) == 3

test_input = { "grid": [[1,3,0],[1,0,0],[1,0,3]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[1,2,2],[1,1,0],[0,1,1]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[1,3,3],[1,0,0],[0,1,0]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[3,2,0],[0,1,0],[0,3,0]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[1,0,4],[2,0,0],[2,0,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,1,3],[3,1,0],[0,1,0]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[3,0,0],[0,2,1],[1,0,2]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[1,0,0],[4,1,1],[0,2,0]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[0,2,3],[2,0,1],[0,1,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[4,0,0],[0,0,2],[3,0,0]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[3,0,0],[4,1,0],[1,0,0]] }
assert my_solution.minimumMoves(**test_input) == 10

test_input = { "grid": [[0,2,1],[1,2,0],[3,0,0]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[1,3,0],[0,0,1],[2,1,1]] }
assert my_solution.minimumMoves(**test_input) == 3

test_input = { "grid": [[3,0,0],[1,0,1],[0,2,2]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[4,2,2],[0,1,0],[0,0,0]] }
assert my_solution.minimumMoves(**test_input) == 10

test_input = { "grid": [[3,2,1],[1,1,0],[1,0,0]] }
assert my_solution.minimumMoves(**test_input) == 9

test_input = { "grid": [[0,3,0],[2,0,0],[1,3,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,0,0],[3,0,0],[4,2,0]] }
assert my_solution.minimumMoves(**test_input) == 13

test_input = { "grid": [[1,1,2],[0,0,0],[0,4,1]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[4,0,0],[0,0,0],[1,2,2]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[1,3,1],[0,0,0],[1,2,1]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[3,1,0],[1,2,2],[0,0,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[2,3,2],[0,1,0],[0,0,1]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[0,1,4],[0,3,0],[0,1,0]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[0,1,0],[1,4,0],[0,3,0]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[0,0,1],[0,0,3],[2,2,1]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[1,0,1],[1,2,0],[1,0,3]] }
assert my_solution.minimumMoves(**test_input) == 3

test_input = { "grid": [[0,0,0],[4,1,2],[1,1,0]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[2,2,1],[0,2,1],[0,1,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[1,0,0],[0,2,0],[4,2,0]] }
assert my_solution.minimumMoves(**test_input) == 10

test_input = { "grid": [[2,0,1],[4,0,0],[0,2,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,0,3],[0,2,0],[1,3,0]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[2,0,1],[1,0,0],[4,0,1]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[0,1,0],[1,0,3],[0,3,1]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,3,1],[0,0,0],[3,1,1]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[3,0,1],[0,3,1],[0,0,1]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[0,4,0],[1,0,0],[0,2,2]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[4,2,0],[0,0,0],[1,1,1]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[0,2,0],[2,1,2],[0,2,0]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[0,1,0],[2,1,1],[4,0,0]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[0,4,1],[1,0,1],[0,0,2]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[1,0,0],[0,0,0],[1,3,4]] }
assert my_solution.minimumMoves(**test_input) == 9

test_input = { "grid": [[0,7,1],[0,1,0],[0,0,0]] }
assert my_solution.minimumMoves(**test_input) == 13

test_input = { "grid": [[0,1,1],[0,2,1],[2,0,2]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[0,2,0],[3,0,0],[3,1,0]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[0,0,0],[2,0,2],[0,2,3]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[0,3,4],[0,1,0],[1,0,0]] }
assert my_solution.minimumMoves(**test_input) == 9

test_input = { "grid": [[1,0,0],[0,0,1],[7,0,0]] }
assert my_solution.minimumMoves(**test_input) == 13

test_input = { "grid": [[0,0,2],[2,0,0],[1,4,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[2,0,1],[1,3,0],[0,2,0]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[1,0,2],[2,3,0],[1,0,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[1,1,2],[0,0,0],[3,1,1]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[0,2,0],[0,1,0],[0,0,6]] }
assert my_solution.minimumMoves(**test_input) == 10

test_input = { "grid": [[1,1,1],[3,0,0],[2,1,0]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[2,0,0],[2,0,1],[3,1,0]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[1,1,0],[0,2,2],[0,3,0]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[1,0,3],[1,1,0],[1,0,2]] }
assert my_solution.minimumMoves(**test_input) == 3

test_input = { "grid": [[1,3,0],[2,0,0],[3,0,0]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[1,0,1],[0,0,1],[0,1,5]] }
assert my_solution.minimumMoves(**test_input) == 10

test_input = { "grid": [[2,0,0],[0,2,1],[1,1,2]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[1,2,3],[1,0,1],[0,0,1]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[0,2,3],[1,0,0],[0,1,2]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[4,1,0],[0,1,1],[2,0,0]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[2,0,1],[1,0,1],[1,2,1]] }
assert my_solution.minimumMoves(**test_input) == 2

test_input = { "grid": [[3,0,3],[0,0,0],[1,1,1]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[0,0,0],[3,4,2],[0,0,0]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[2,1,2],[0,0,1],[3,0,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[1,0,0],[0,3,3],[0,0,2]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[0,2,0],[1,0,1],[1,3,1]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[0,1,0],[2,0,4],[1,0,1]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[1,0,3],[0,0,2],[0,1,2]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[2,1,1],[0,0,0],[0,1,4]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[2,0,1],[0,2,0],[1,3,0]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[2,0,2],[0,0,2],[0,0,3]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,2,2],[2,0,1],[1,1,0]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[0,0,1],[2,3,2],[1,0,0]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[1,1,0],[3,0,4],[0,0,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[1,0,0],[0,0,0],[5,1,2]] }
assert my_solution.minimumMoves(**test_input) == 11

test_input = { "grid": [[1,0,0],[3,5,0],[0,0,0]] }
assert my_solution.minimumMoves(**test_input) == 9

test_input = { "grid": [[3,1,1],[1,1,0],[2,0,0]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[0,1,3],[0,0,1],[1,2,1]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,0,0],[1,2,0],[3,0,3]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[0,0,0],[1,2,2],[2,0,2]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[4,0,0],[2,3,0],[0,0,0]] }
assert my_solution.minimumMoves(**test_input) == 10

test_input = { "grid": [[1,1,0],[1,0,1],[4,1,0]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[0,0,1],[0,1,2],[1,0,4]] }
assert my_solution.minimumMoves(**test_input) == 10

test_input = { "grid": [[0,1,3],[2,0,0],[0,3,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,0,0],[5,0,1],[1,1,1]] }
assert my_solution.minimumMoves(**test_input) == 7

test_input = { "grid": [[0,1,1],[0,0,3],[2,1,1]] }
assert my_solution.minimumMoves(**test_input) == 5

test_input = { "grid": [[2,0,1],[0,0,1],[2,2,1]] }
assert my_solution.minimumMoves(**test_input) == 3

test_input = { "grid": [[3,0,2],[2,1,0],[0,0,1]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,0,2],[0,0,2],[4,0,1]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[3,0,0],[0,2,0],[0,0,4]] }
assert my_solution.minimumMoves(**test_input) == 8

test_input = { "grid": [[0,1,3],[1,0,0],[0,4,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[2,1,2],[0,2,1],[1,0,0]] }
assert my_solution.minimumMoves(**test_input) == 4

test_input = { "grid": [[0,0,2],[1,0,3],[1,0,2]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[0,2,2],[0,1,4],[0,0,0]] }
assert my_solution.minimumMoves(**test_input) == 10

test_input = { "grid": [[1,0,1],[0,0,5],[1,1,0]] }
assert my_solution.minimumMoves(**test_input) == 6

test_input = { "grid": [[3,1,0],[0,0,0],[0,1,4]] }
assert my_solution.minimumMoves(**test_input) == 8