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

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
# [[1,1,1],
#  [1,1,1],
#  [1,1,1]]

# [[0,2,1],
#  [1,1,1],
#  [1,1,1]] 5
        def gridToTuple(grid:List[List[int]]) -> tuple:
            return tuple(tuple(row) for row in grid)
        
        def anyZeroLeft(tup: tuple) -> bool:
            # print("tup={}".format(tup))
            for i in range(len(tup)):
                for j in range(len(tup[0])):
                    if tup[i][j] == 0:
                        return True 
            return False 
            
        neighbors = [(0, -1), (-1, 0), (0, 1), (1, 0)]
        visited = set()
        queue = collections.deque([gridToTuple(grid)])
        # print("grid={}, queue={}".format(grid, queue))
        steps = 0
        while queue:
            nextQueue = collections.deque()
            while queue:
                status = queue.popleft()
                if status in visited:
                    continue 
                if not anyZeroLeft(status):
                    return steps 
                
                visited.add(status)
                # print("visited={}, steps={}".format(visited, steps))
                for i in range(len(status)):
                    for j in range(len(status[0])):
                        cell = status[i][j]
                        if cell <= 1:
                            continue 
                        # print("i={}, j={}".format(i, j))
                        for nei in neighbors:
                            ni = i + nei[0]
                            nj = j + nei[1]
                            if 0 <= ni < 3 and 0 <= nj < 3:
                                nxtstatus = list(list(row) for row in status)
                                nxtstatus[i][j] -= 1
                                nxtstatus[ni][nj] += 1
                                nxttup = gridToTuple(nxtstatus)
                                if nxttup in visited:
                                    continue 
                                nextQueue.append(nxttup)
            queue = nextQueue 
            steps += 1
            # print("hi")
        return steps
            
                    
            
19800