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

Posted on In Views:

1，问题描述

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

难度：中等

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

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

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

示例 1：

img

1
2
3
4
5
6
7
8
输入：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：

img

1
2
3
4
5
6
7
8
9
输入：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 。

2，初步思考

​ 模拟法直接暴力求解，找出所有可能的结果，比较后取最小值；同时还有一个扩展知识47. 全排列 II的概念。

3，代码处理

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import java.util.*;

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

    // 暴力搜索，适合最小长度，移动次数
    public int minimumMoves_brute(int[][] grid) {
        this.grid = grid;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int idx = i * 3 + j;//坐标转换
                if (grid[i][j] > 1) {
                    while (grid[i][j] > 1) {
                        grid[i][j]--;
                        provider.add(idx);
                    }
                }
                if (grid[i][j] < 1) {
                    receiver.add(idx);
                }
            }
        }
        int min = Integer.MAX_VALUE;
        List<List<Integer>> lists = permuteUnique_gov(provider);
        for (List<Integer> list : lists) {
            int step = 0;
            for (int i = 0; i < list.size(); i++) {
                step += Math.abs(
                        list.get(i) / 3 - receiver.get(i) / 3
                );
                step += Math.abs(
                        list.get(i) % 3 - receiver.get(i) % 3
                );
            }
            min = Math.min(min, step);
        }
        return min;
    }

    private List<List<Integer>> permuteUnique_gov(List<Integer> nums) {
        List<List<Integer>> res = new ArrayList<>();
        Collections.sort(nums);
        backtrack(nums.size(), 0, nums, res);
        return res;
    }

    private void backtrack(int len, int index, List<Integer> output, List<List<Integer>> res) {
        if (index == len) res.add(new ArrayList<>(output));
        Set<Integer> set = new HashSet<>();
        for (int i = index; i < len; i++) {
            if (set.contains(output.get(i))) {// 已经使用过的数据直接跳过即可
                continue;
            }
            set.add(output.get(i));
            Collections.swap(output, index, i);// 交换位置，递归处理
            backtrack(len, index + 1, output, res);
            Collections.swap(output, index, i);// 恢复原样
        }
    }


    List<Integer> provider = new ArrayList<>();
    List<Integer> receiver = new ArrayList<>();
    int ret;
    int[][] grid;

    public int minimumMoves(int[][] grid) {
        this.grid = grid;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int idx = i * 3 + j;//坐标转换
                if (grid[i][j] > 1) {
                    provider.add(idx);
                }
                if (grid[i][j] < 1) {
                    receiver.add(idx);
                }
            }
        }
        ret = Integer.MAX_VALUE;
        dfs(0, 0);
        return ret;
    }

    // 深度优先搜索，适合最小长度、移动次数(本质也是遍历)
    public void dfs(int receiverIdx, int steps) {
        if (receiverIdx == receiver.size()) {
            ret = Math.min(ret, steps);
            return;
        }
        int receiverX = receiver.get(receiverIdx) / 3;
        int receiverY = receiver.get(receiverIdx) % 3;
        for (int providerIdx : provider) {
            int providerX = providerIdx / 3;
            int providerY = providerIdx % 3;

            if (grid[providerX][providerY] > 1) {
                grid[providerX][providerY]--;
                dfs(receiverIdx + 1, steps + Math.abs(receiverX - providerX) + Math.abs(receiverY - providerY));
                grid[providerX][providerY]++;
            }
        }
    }

    public static void main(String[] args) {
        _2850将石头分散到网格图的最少移动次数 solution = new _2850将石头分散到网格图的最少移动次数();
        System.out.println(solution.minimumMoves_brute(new int[][]{
                {1, 1, 0},
                {1, 1, 1},
                {1, 2, 1}}));
    }
}