<p>You are given a <strong>0-indexed</strong> 2D integer matrix <code>grid</code> of size <code>3 * 3</code>, representing the number of stones in each cell. The grid contains exactly <code>9</code> stones, and there can be <strong>multiple</strong> stones in a single cell.</p>

<p>In one move, you can move a single stone from its current cell to any other cell if the two cells share a side.</p>

<p>Return <em>the <strong>minimum number of moves</strong> required to place one stone in each cell</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/08/23/example1-3.svg" style="width: 401px; height: 281px;" />
<pre>
<strong>Input:</strong> grid = [[1,1,0],[1,1,1],[1,2,1]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2023/08/23/example2-2.svg" style="width: 401px; height: 281px;" />
<pre>
<strong>Input:</strong> grid = [[1,3,0],[1,0,0],[1,0,3]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>grid.length == grid[i].length == 3</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 9</code></li>
	<li>Sum of <code>grid</code> is equal to <code>9</code>.</li>
</ul>

from collections import deque

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        # Flatten the grid into a 1D list for easier manipulation
        start = [grid[i][j] for i in range(3) for j in range(3)]
        
        # Target configuration: each cell contains exactly one stone
        target = [1] * 9
        
        # Convert the grid to a string for hashing
        start_str = ''.join(map(str, start))
        target_str = ''.join(map(str, target))
        
        # BFS queue: (current configuration, number of moves)
        queue = deque([(start_str, 0)])
        
        # Set to keep track of visited configurations
        visited = set([start_str])
        
        # Define the possible moves (cells that share a side)
        moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        while queue:
            current, moves_made = queue.popleft()
            
            if current == target_str:
                return moves_made
            
            # Convert the string back to a list for manipulation
            current_list = [int(x) for x in current]
            
            # Find the indices of cells with more than one stone
            overflow_indices = [i for i, x in enumerate(current_list) if x > 1]
            
            for idx in overflow_indices:
                r, c = idx // 3, idx % 3
                
                for dr, dc in moves:
                    nr, nc = r + dr, c + dc
                    new_idx = nr * 3 + nc
                    
                    # Check if the new position is within bounds
                    if 0 <= nr < 3 and 0 <= nc < 3:
                        # Create a new configuration by moving the stone
                        new_list = current_list[:]
                        new_list[idx] -= 1
                        new_list[new_idx] += 1
                        new_str = ''.join(map(str, new_list))
                        
                        if new_str not in visited:
                            visited.add(new_str)
                            queue.append((new_str, moves_made + 1))
        
        # If no solution is found, return -1 (not possible in this case)
        return -1

# Example usage:
solution = Solution()
grid = [[1, 1, 0], [1, 1, 1], [1, 2, 1]]
print(solution.minimumMoves(grid))  # Output: 3

grid = [[1, 3, 0], [1, 0, 0], [1, 0, 3]]
print(solution.minimumMoves(grid))  # Output: 4
17900