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

题目

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 。

题解

方法一：

思路

暴力枚举

用了各种贪心策略发现都不能通过。

由于数据量极小，用非多项式时间复杂度的暴力方法也能通过。

记录每个值为0的点，以及每个值大于1的点，若值为x则记录x次。

这样得到两个长度都为n的数组，考虑他们的匹配，会发现有n!种情况。对于每种情况计算各个对应点的曼哈顿距离之和，取最小值作为答案。

这里n!种情况，其实就是求全排列。

代码

class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int,int>> a, b;
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                if (grid[i][j] == 0) a.emplace_back(i,j);
                while (grid[i][j] > 1) b.emplace_back(i,j), grid[i][j]--;
            }
        }
        
        int n = a.size();
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        
        int ans = 10000;
        while (1) {
            int tans = 0;
            for (int i=0; i<n; i++) {
                auto [x1, y1] = a[p[i]];
                auto [x2, y2] = b[i];
                tans += abs(x1-x2)+abs(y1-y2);
            }
            ans = min(ans, tans);
            if (is_sorted(p.begin(), p.end(), greater<int>())) break;
            next_permutation(p.begin(), p.end());
        }
        
        // int n = a.size();
        // int ans = 10000;
        // vector<int> h(n);
        // vector<int> p;
        // function<void()> dfs = [&]() {
        //     if (p.size() == n) {
        //         int tans = 0;
        //         for (int i=0; i<n; i++) {
        //             auto [x1, y1] = a[p[i]];
        //             auto [x2, y2] = b[i];
        //             tans += abs(x1-x2)+abs(y1-y2);
        //         }
        //         ans = min(ans, tans);
        //         return ;
        //     }
        //     for (int i=0; i<n; i++) {
        //         if (h[i]) continue;
        //         h[i] = 1;
        //         p.push_back(i);
        //         dfs();
        //         p.pop_back();
        //         h[i] = 0;
        //     }
        // };
        // dfs();
        
        return ans;
        
    }
};