<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
from typing import List

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        # target = [[1] * cols for _ in range(rows)]  # Target grid with each cell having exactly 1 stone

        # Helper to check if current grid is the target grid
        def is_goal_state(g):
            return all(g[i][j] == 1 for i in range(rows) for j in range(cols))

        # Initialize the BFS queue with the current grid state and zero moves
        start = tuple(tuple(row) for row in grid)
        queue = deque([(start, 0)])  # (current grid state, move count)
        visited = set()
        visited.add(start)

        # Directions for moving stones
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while queue:
            current_grid, moves = queue.popleft()

            # Convert current_grid back to 2D list
            current_grid_list = [list(row) for row in current_grid]

            if is_goal_state(current_grid_list):
                return moves

            for x in range(rows):
                for y in range(cols):
                    if current_grid_list[x][y] > 1:
                        for dx, dy in directions:
                            x_, y_ = x + dx, y + dy
                            if 0 <= x_ < rows and 0 <= y_ < cols:
                                # Create a new grid configuration
                                new_grid = [row[:] for row in current_grid_list]
                                new_grid[x][y] -= 1
                                new_grid[x_][y_] += 1

                                # Convert new grid to tuple and check if it's been visited
                                new_grid_tuple = tuple(tuple(row) for row in new_grid)
                                if new_grid_tuple not in visited:
                                    visited.add(new_grid_tuple)
                                    queue.append((new_grid_tuple, moves + 1))

        return -1  # Return -1 if no solution is found

# class Solution:
#     def minimumMoves(self, grid: List[List[int]]) -> int:
#         queue = deque()
#         rows, cols = len(grid), len(grid[0])
#         moves = 0
#         for i in range(rows):
#             for j in range(cols):
#                 if grid[i][j] > 1:
#                     queue.append((i, j))
#         while queue:
#             x, y = queue.popleft()
#             for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
#                 x_, y_ = x + dx, y + dy
#                 if x_ >= 0 and x_ < rows and y_ >= 0 and y_ < cols:
#                     grid[x][y] -= 1  # Give a stone to its neighbor
#                     grid[x_][y_] += 1
#                     # If this grid doesn't need a stone, it will be giving stones to its neighbors later
#                     if grid[x_][y_] > 1:
#                         queue.append((x_, y_))
#                     # If the original grid still has more than one stone, push it to the queue again
#                     if grid[x][y] > 1:
#                         queue.append((x, y))
#             moves += 1



# from collections import deque
# from typing import List

# class Solution:
#     def minimumMoves(self, grid: List[List[int]]) -> int:
#         queue = deque()
#         rows, cols = len(grid), len(grid[0])
#         moves = 0
        
#         # Start by adding all cells with more than one stone to the queue
#         for i in range(rows):
#             for j in range(cols):
#                 if grid[i][j] > 1:
#                     queue.append((i, j))
        
#         while queue:
#             x, y = queue.popleft()
#             for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
#                 x_, y_ = x + dx, y + dy
#                 if 0 <= x_ < rows and 0 <= y_ < cols:
#                     while grid[x][y] > 1:
#                         grid[x][y] -= 1  # Take one stone from (x, y)
#                         grid[x_][y_] += 1  # Give one stone to (x_, y_)
#                         moves += 1  # Increase the move count
                        
#                         # If the new cell (x_, y_) now has more than one stone, add it to the queue
#                         if grid[x_][y_] > 1:
#                             queue.append((x_, y_))
            
#             # If the original cell (x, y) still has more than one stone after the loop, re-add it to the queue
#             if grid[x][y] > 1:
#                 queue.append((x, y))
        
#         return moves

19100