<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:
        # multiple origins and multiple destinations
        # any node that has greater than 1 stone, find nearest 0s using bfs and dump it
        # what if a node has multiple close points and only 1 stone to dump while another node has to choose excatly one to minimize
        # we can also use backtracking for every close point to ensure we find minm

        # Can additionally keep a list of zeros and extras to make it easier??

        stones = []
        zeros = []
        for i in range(3):
            for j in range(3):
                if grid[i][j] > 1:
                    stones.append([i, j, grid[i][j]])
                if grid[i][j] == 0:
                    zeros.append((i,j))
        ans = float('inf')
        memo = {}
        
        def minMove(slice, moves, z):
            if len(z) == 0:
                nonlocal ans
                ans = min(ans , moves)
                return 
            state = (tuple(tuple(row) for row in stones), tuple(z))
            if state in memo and memo[state] <= moves:
                return
            memo[state] = moves
            for i in range(slice, len(stones)):
                no = stones[i][2]
                x, y = stones[i][0], stones[i][1]
                for t in range(no-1):
                    # each extra stone will be placed at some zero
                    stones[i][2] -= 1
                    for j in range(len(z)):
                        zero = z[:]
                        m1, m2 = zero.pop(j)
                        minMove(slice+int(stones[i][2]==0), abs(x-m1)+abs(y-m2)+moves,zero)
                # after trying to place this stone[i][2] in every possible config, retain its value for next iteration
                stones[i][2] = no
        minMove(0, 0, zeros[:])
        return ans

20100