将石头分散到网格图的最少移动次数

难度: Medium

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有多个石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

示例 1：

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]
输出：3
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。
2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。
总共需要 3 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 3 。

示例 2：

输入：grid = [[1,3,0],[1,0,0],[1,0,3]]
输出：4
解释：让每个格子都有一个石头的一个操作序列为：
1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。
2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。
3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。
4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。
总共需要 4 次操作让每个格子都有一个石头。
让每个格子都有一个石头的最少操作次数为 4 。

提示：

grid.length == grid[i].length == 3
0 <= grid[i][j] <= 9
grid 中元素之和为 9 。

Submission

运行时间: 55 ms

内存: 16.2 MB

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        zero = []
        move = []
        for i in range(3):
            for j in range(3):
                if grid[i][j] == 0:
                    zero.append([i,j])
                elif grid[i][j] > 1:
                    move.append([i,j])
        
        ans  = 1000
        n = len(zero)
        def dfs(i, count):
            nonlocal ans
            if i == n:
                ans = min(ans, count)
                return 

            for row, col in move:
                r,c = zero[i]
                if grid[row][col] > 1:
                    grid[row][col] -= 1
                    dfs(i+1, count+abs(r-row)+abs(c - col))
                    grid[row][col] += 1
        dfs(0,0)
        return ans

Explain

题目的目标是通过最少的移动，将每个格子中的石头数量均匀为一个。这个题解采用了深度优先搜索（DFS）的策略来尝试所有可能的石头移动方式。首先，题解通过两次遍历找出所有需要石头（即空格子）和多余石头的格子。然后，使用DFS尝试所有可能的从多余石头格子到空格子的移动方式，每次移动都更新当前的移动总次数，并在所有格子都被填满后记录最小的移动次数。DFS过程中，每次尝试将一个石头从一个有多余石头的格子移动到一个空格子，然后递归处理下一个空格子，直到所有空格子都被处理完毕。

时间复杂度: O((M*N)^2)

空间复杂度: O(N)

# Solution class definition

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        zero = []  # 存储空格子的坐标
        move = []  # 存储有多余石头的格子的坐标
        for i in range(3):
            for j in range(3):
                if grid[i][j] == 0:
                    zero.append([i, j])
                elif grid[i][j] > 1:
                    move.append([i, j])
        
        ans = 1000  # 初始化最小移动次数为一个大数
        n = len(zero)  # 空格子的数量
        
        def dfs(i, count):
            nonlocal ans
            if i == n:
                ans = min(ans, count)  # 所有空格子都处理完毕，更新最小移动次数
                return 
            
            for row, col in move:
                r, c = zero[i]
                if grid[row][col] > 1:
                    grid[row][col] -= 1  # 从多余石头格子移除一个石头
                    dfs(i+1, count + abs(r - row) + abs(c - col))  # 递归处理下一个空格子
                    grid[row][col] += 1  # 回溯，恢复石头数
        dfs(0, 0)
        return ans

Explore

在DFS的实现中，通过一个递归函数确保每个空格子被处理。函数中有一个递归的终止条件，当空格子的索引等于空格子总数时，表示所有空格子已被处理。每次递归调用都会尝试将一个石头从多余的格子移动到当前处理的空格子，并递归地处理下一个空格子，这样可以确保每个空格子都被逐一填满。

在当前的DFS实现中，避免重复处理相同的移动组合的策略主要依靠回溯。在每次递归调用之后，会将石头数恢复到移动前的状态，这种方式称为回溯。此外，更高效的策略可以包括使用记忆化来存储已经计算过的状态，或者使用更先进的搜索策略（如广度优先搜索）来减少不必要的重复搜索。

题解中的DFS方法主要关注于尝试所有可能的移动，以找出完成任务的最少移动次数，而不是每次都寻找最短的单次移动路径。每次移动都计算距离并加到总移动次数中，但此策略并不保证每一步都是最优的。若要优化每次移动的效率，可以考虑引入贪心算法或启发式搜索（如A*算法）来优先考虑最有可能快速达到目标的移动。