<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, G):
      M, N = 3, 3
      min_moves = sys.maxsize
      zero_arr, big_arr = [], []

      for m in range(M):
        for n in range(N):
          if G[m][n] == 0:
            zero_arr.append([m, n])
          if G[m][n] > 1:
            big_arr.append([m, n])
      
      def iterate(zero_idx, cur_moves):
        nonlocal min_moves
        if zero_idx == len(zero_arr):
          min_moves = min(min_moves, cur_moves)
          return
        
        zm, zn = zero_arr[zero_idx]
        for bm, bn in big_arr:
          if G[bm][bn] > 1:
            G[bm][bn] -= 1
            iterate(zero_idx + 1, cur_moves + abs(bm - zm) + abs(zn - bn))
            G[bm][bn] += 1
        
      iterate(0, 0)
      return min_moves        




'''
    def minimumMoves(self, G):
      min_moves = sys.maxsize
      M, N = 3, 3
      zs, bs = [] , []
      for m in range(M):
        for n in range(N):
          if G[m][n] == 0:
            zs.append((m, n))
          elif G[m][n] > 1:
            bs.append((m, n))
      
      def iterate_moves(zero_idx, cur_moves):
        nonlocal min_moves
        if zero_idx == len(zs):
          min_moves = min(min_moves, cur_moves)
          return
      
        zm, zn = zs[zero_idx]
        for (bm, bn) in bs:
          if G[bm][bn] > 1:
            G[bm][bn] -= 1
            iterate_moves(zero_idx+1, cur_moves + abs(bm - zm) + abs(bn - zn))
            G[bm][bn] += 1
      
      iterate_moves(0, 0)
      return min_moves
'''
16500