Distribute Nine Stones Across a Three-by-Three Grid
Company: American Express
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Distribute Nine Stones Across a Three-by-Three Grid
You are given a 0-indexed `3 x 3` integer matrix `grid`, whose entries are the numbers of stones in its cells. There are exactly nine stones in total, and a cell may initially hold more than one stone.
One move transfers a single stone to a cell sharing a side with its current cell. Return the minimum number of moves needed to leave exactly one stone in every cell.
### Examples
**Example 1**
```text
Input: grid = [[2,0,1],[1,1,1],[1,1,1]]
Output: 1
```
Move one stone from `(0,0)` to `(0,1)`. The grid was not already complete, so at least one move is needed, and this single move finishes it.
**Example 2**
```text
Input: grid = [[0,2,1],[1,1,1],[2,1,0]]
Output: 3
```
Move one extra stone from `(0,1)` to `(0,0)`, then move an extra stone from `(2,0)` through `(2,1)` to `(2,2)`. These transfers cost one and two moves. Each initially empty cell needs a stone, and its closest possible surplus source is respectively one and two steps away, so fewer than three total moves cannot suffice.
### Constraints
- `grid.length == grid[i].length == 3`.
- `0 <= grid[i][j] <= 9`.
- The sum of all entries of `grid` is exactly `9`.
### Clarifying Questions
- Is a diagonal transfer one move? No; cells must share a side.
- Can an occupied cell receive a stone temporarily? Yes; multiple stones per cell are allowed while moving them.
- Can a stone travel through intermediate cells? Yes; every side-adjacent step costs one move.
- Is the target merely to make every cell nonempty? With exactly nine stones and nine cells, the required final state is exactly one per cell.
### C++ Interface
```cpp
class Solution {
public:
int minimumMoves(vector<vector<int>>& grid) {
}
};
```
### Reasoning Checkpoints
- Preserve the total number of stones and distinguish initial surpluses from empty cells.
- Account for transfers involving more than one step and occupied intermediate cells.
- Justify a global minimum rather than committing to an arbitrary nearest transfer.
```hint Surplus and deficit
After reserving one stone at each initially occupied cell, how many extra stones remain, and which cells still need one?
```
Overview: Find the fewest side-adjacent single-stone moves that distribute exactly nine stones into one per cell of a three-by-three grid.