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

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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

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

给你一个大小为 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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-22 21:35:28
 */
public int minimumMoves(int[][] grid) {
  int row = grid.length;
  int column = grid[0].length;
  List<int[]> more = new ArrayList<>(row * column);
  List<int[]> less = new ArrayList<>(row * column);
  for (int r = 0; r < row; r++) {
    for (int c = 0; c < column; c++) {
      if (grid[r][c] > 1) {
        for (int i = 1; i < grid[r][c]; i++) {
          more.add(new int[]{r, c});
        }
      } else if (grid[r][c] == 0) {
        less.add(new int[]{r, c});
      }
    }
  }
  List<List<int[]>> permutations = permutations(more);
  int result = Integer.MAX_VALUE;
  for (List<int[]> perm : permutations) {
    int distance = 0;
    for (int i = 0; i < less.size(); i++) {
      int[] start = perm.get(i);
      int[] end = less.get(i);
      distance += (Math.abs(end[0] - start[0]) + Math.abs(end[1] - start[1]));
    }
    result = Math.min(result, distance);
  }
  return result;
}

private List<List<int[]>> permutations(List<int[]> points) {
  List<List<int[]>> result = new ArrayList<>();
  List<int[]> path = new ArrayList<>();
  boolean[] used = new boolean[points.size()];
  permutations(points, result, path, used);
  return result;
}

private void permutations(List<int[]> points, List<List<int[]>> result,
                          List<int[]> path, boolean[] used) {
  if (path.size() == points.size()) {
    result.add(new ArrayList<>(path));
    return;
  }
  for (int i = 0; i < points.size(); i++) {
    if (used[i]) {
      continue;
    }
    used[i] = true;
    path.add(points.get(i));
    permutations(points, result, path, used);
    path.removeLast();
    used[i] = false;
  }
}

参考资料

2850. 将石头分散到网格图的最少移动次数 - 两种方法：枚举全排列 / 最小费用最大流 — 讲解比官方题解更易懂。