<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 get_moves(self, i0, j0, i1, j1):
        return abs(i0 - i1) + abs(j0 - j1) 
    # def bfs(self, i, j, grid):
    #     cur_moves = 0
    #     cur_que = deque([[i, j]])
    #     visited = [[False for c in range(3)] for r in range(3)]
    #     visited[i][j] = True
    #     while cur_que:
    #         for que_ind in range(len(cur_que)):
    #             cur_i, cur_j = cur_que.popleft()
    #             if grid[cur_i][cur_j] > 1:
    #                 grid[cur_i][cur_j] -= 1
    #                 grid[i][j] += 1
    #                 return cur_moves
            
    #             if cur_i > 0 and not visited[cur_i - 1][cur_j]:
    #                 cur_que.append([cur_i - 1, cur_j])
    #                 visited[cur_i - 1][cur_j] = True
    #             if cur_i < 2 and not visited[cur_i + 1][cur_j]:
    #                 cur_que.append([cur_i + 1, cur_j])
    #                 visited[cur_i + 1][cur_j] = True
    #             if cur_j > 0 and not visited[cur_i][cur_j - 1]:
    #                 cur_que.append([cur_i, cur_j - 1])
    #                 visited[cur_i][cur_j - 1] = True
    #             if cur_j < 2 and not visited[cur_i][cur_j + 1]:
    #                 cur_que.append([cur_i, cur_j + 1])
    #                 visited[cur_i][cur_j + 1] = True

    #         cur_moves += 1
        
    #     return cur_moves

    def minimumMoves(self, grid: List[List[int]]) -> int:
        # n_moves = 0

        # for i in range(3):
        #     for j in range(3):
        #         if grid[i][j] == 0:
        #             n_moves += self.bfs(i, j, grid)
        
        # return n_moves

        zero_locs = []
        spare_locs = []

        for i, j in product(range(3), range(3)):
            stone = grid[i][j]

            if stone == 0:
                zero_locs.append([i, j])
            if stone > 1:
                spare_locs += [[i, j] for s in range(stone - 1)]
            
        perms = list(permutations(spare_locs))

        min_steps = 2**31 - 1
        for p in perms:
            cur_steps = 0
            for z_id, z_pos in enumerate(zero_locs):
                cur_steps += self.get_moves(p[z_id][0], p[z_id][1], z_pos[0], z_pos[1])
            if cur_steps < min_steps:
                min_steps = cur_steps
        return min_steps
21600