<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:
        surplus_positions = []
        deficit_positions = []
        
        # 收集多余石子和缺少石子的位置
        for i in range(3):
            for j in range(3):
                count = grid[i][j]
                if count > 1:
                    surplus_positions.extend([(i, j)] * (count - 1))
                elif count == 0:
                    deficit_positions.append((i, j))
        
        n = len(surplus_positions)
        m = len(deficit_positions)
        
        # 如果没有多余或缺少的石子，直接返回0
        if n == 0:
            return 0
        
        # 构建代价矩阵
        cost = [ [0] * m for _ in range(n) ]
        for i in range(n):
            for j in range(m):
                si, sj = surplus_positions[i]
                di, dj = deficit_positions[j]
                cost[i][j] = abs(si - di) + abs(sj - dj)
        
        # 应用匈牙利算法
        return self.hungarian(cost)
    
    def hungarian(self, cost):
        n = len(cost)
        m = len(cost[0])
        u = [0] * (n + 1)
        v = [0] * (m + 1)
        p = [0] * (m + 1)
        way = [0] * (m + 1)
        
        INF = float('inf')
        for i in range(1, n + 1):
            p[0] = i
            minv = [INF] * (m + 1)
            used = [False] * (m + 1)
            j0 = 0
            while True:
                used[j0] = True
                i0 = p[j0]
                delta = INF
                j1 = -1
                for j in range(1, m + 1):
                    if not used[j]:
                        cur = cost[i0 - 1][j - 1] - u[i0] - v[j]
                        if cur < minv[j]:
                            minv[j] = cur
                            way[j] = j0
                        if minv[j] < delta:
                            delta = minv[j]
                            j1 = j
                for j in range(m + 1):
                    if used[j]:
                        u[p[j]] += delta
                        v[j] -= delta
                    else:
                        minv[j] -= delta
                j0 = j1
                if p[j0] == 0:
                    break
            # 增广路径
            while True:
                j1 = way[j0]
                p[j0] = p[j1]
                j0 = j1
                if j0 == 0:
                    break
        # 计算答案
        ans = -v[0]
        return int(ans)
        

16700