# 2850. Minimum Moves to Spread Stones Over Grid

## Problem Statement

<br>

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

&#x20;

**Example 1:**

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

<pre><code><strong>Input: grid = [[1,1,0],[1,1,1],[1,2,1]]
</strong><strong>Output: 3
</strong><strong>Explanation: One possible sequence of moves to place one stone in each cell is: 
</strong>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.
</code></pre>

**Example 2:**

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

<pre><code><strong>Input: grid = [[1,3,0],[1,0,0],[1,0,3]]
</strong><strong>Output: 4
</strong><strong>Explanation: One possible sequence of moves to place one stone in each cell is:
</strong>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.
</code></pre>

&#x20;

**Constraints:**

* `grid.length == grid[i].length == 3`
* `0 <= grid[i][j] <= 9`
* Sum of `grid` is equal to `9`.

## Intuition

```
Here BFS wont work, as stone collection is dependent on other

So we use Recursion and try all ways
```

### Links

<https://leetcode.com/problems/minimum-moves-to-spread-stones-over-grid/description/>

### Video Links

<https://www.youtube.com/watch?v=Ew3C223hd-E&ab_channel=AryanMittal>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<vector<int>> xtra,zero;
    int ret;
    void solve(int i, int count){
        if(i>=zero.size()){
            ret = min(ret, count);
            return;
        }

        for(int k=0; k<xtra.size(); k++){
            if(xtra[k][2] ==0)  continue;
            xtra[k][2]--;
            solve(i+1, abs(xtra[k][0] - zero[i][0]) + abs(xtra[k][1]-zero[i][1]) + count);
            xtra[k][2]++;
        }
    }

    int minimumMoves(vector<vector<int>>& grid) {
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(grid[i][j] == 0)
                    zero.push_back({i,j});
                else if(grid[i][j] > 1)
                    xtra.push_back({i,j,grid[i][j]-1});
            }
        }

        if(zero.size() == 0)    return 0;
        ret = INT_MAX;
        solve(0,0);

        return ret;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###