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 。

解题思路

这是一个经典的分配问题，需要将多余的石头分配给缺石头的位置，使得移动次数最小。

核心思路：

  1. 识别源点和目标点：找出所有石头数量 > 1 的位置（源点）和石头数量 = 0 的位置（目标点）
  2. 回溯 + 剪枝：对于每个目标点，尝试从所有可能的源点获取石头，计算曼哈顿距离作为移动成本
  3. 状态压缩优化：可以用位掩码表示哪些源点已被使用

算法流程：

  • 遍历网格，收集所有多余石头的位置和缺少石头的位置
  • 使用回溯算法，为每个空位置分配一个有多余石头的位置
  • 计算分配方案的总移动距离（曼哈顿距离之和）
  • 返回所有可能分配方案中的最小值

复杂度考虑： 根据题目提示，最多有4个位置有多余石头，空位置数量等于多余石头数量，所以时间复杂度为 O(4^4) = O(256)，完全可以接受。

推荐解法：回溯法，代码简洁且易于理解。

代码实现

class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int, int>> sources, targets;
        
        // 找出所有多余石头的位置和空位置
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] > 1) {
                    for (int k = 1; k < grid[i][j]; k++) {
                        sources.push_back({i, j});
                    }
                } else if (grid[i][j] == 0) {
                    targets.push_back({i, j});
                }
            }
        }
        
        return backtrack(sources, targets, 0);
    }
    
private:
    int backtrack(vector<pair<int, int>>& sources, vector<pair<int, int>>& targets, int idx) {
        if (idx == targets.size()) {
            return 0;
        }
        
        int minMoves = INT_MAX;
        for (int i = 0; i < sources.size(); i++) {
            int dist = abs(sources[i].first - targets[idx].first) + 
                      abs(sources[i].second - targets[idx].second);
            
            // 移除当前源点，继续递归
            auto temp = sources[i];
            sources.erase(sources.begin() + i);
            
            minMoves = min(minMoves, dist + backtrack(sources, targets, idx + 1));
            
            // 回溯
            sources.insert(sources.begin() + i, temp);
        }
        
        return minMoves;
    }
};

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        sources, targets = [], []
        
        # 找出所有多余石头的位置和空位置
        for i in range(3):
            for j in range(3):
                if grid[i][j] > 1:
                    for _ in range(grid[i][j] - 1):
                        sources.append((i, j))
                elif grid[i][j] == 0:
                    targets.append((i, j))
        
        def backtrack(idx):
            if idx == len(targets):
                return 0
            
            min_moves = float('inf')
            for i in range(len(sources)):
                # 计算曼哈顿距离
                dist = abs(sources[i][0] - targets[idx][0]) + abs(sources[i][1] - targets[idx][1])
                
                # 移除当前源点，继续递归
                temp = sources.pop(i)
                min_moves = min(min_moves, dist + backtrack(idx + 1))
                # 回溯
                sources.insert(i, temp)
            
            return min_moves
        
        return backtrack(0)

public class Solution {
    public int MinimumMoves(int[][] grid) {
        var sources = new List<(int, int)>();
        var targets = new List<(int, int)>();
        
        // 找出所有多余石头的位置和空位置
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid[i][j] > 1) {
                    for (int k = 1; k < grid[i][j]; k++) {
                        sources.Add((i, j));
                    }
                } else if (grid[i][j] == 0) {
                    targets.Add((i, j));
                }
            }
        }
        
        return Backtrack(sources, targets, 0);
    }
    
    private int Backtrack(List<(int, int)> sources, List<(int, int)> targets, int idx) {
        if (idx == targets.Count) {
            return 0;
        }
        
        int minMoves = int.MaxValue;
        for (int i = 0; i < sources.Count; i++) {
            int dist = Math.Abs(sources[i].Item1 - targets[idx].Item1) + 
                      Math.Abs(sources[i].Item2 - targets[idx].Item2);
            
            // 移除当前源点，继续递归
            var temp = sources[i];
            sources.RemoveAt(i);
            
            minMoves = Math.Min(minMoves, dist + Backtrack(sources, targets, idx + 1));
            
            // 回溯
            sources.Insert(i, temp);
        }
        
        return minMoves;
    }
}

var minimumMoves = function(grid) {
    const sources = [];
    const targets = [];
    
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (grid[i][j] === 0) {
                targets.push([i, j]);
            } else if (grid[i][j] > 1) {
                for (let k = 0; k < grid[i][j] - 1; k++) {
                    sources.push([i, j]);
                }
            }
        }
    }
    
    function getPermutations(arr) {
        if (arr.length <= 1) return [arr];
        const result = [];
        for (let i = 0; i < arr.length; i++) {
            const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
            const perms = getPermutations(rest);
            for (const perm of perms) {
                result.push([arr[i], ...perm]);
            }
        }
        return result;
    }
    
    function manhattanDistance(a, b) {
        return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
    }
    
    let minMoves = Infinity;
    const sourcePerms = getPermutations(sources);
    
    for (const perm of sourcePerms) {
        let moves = 0;
        for (let i = 0; i < targets.length; i++) {
            moves += manhattanDistance(perm[i], targets[i]);
        }
        minMoves = Math.min(minMoves, moves);
    }
    
    return minMoves;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n!)n 为空位置数量，最坏情况下为 4，实际为 4! = 24
空间复杂度O(n)递归栈深度和存储源点、目标点的空间

相关题目