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. 题目中已经确定了矩阵是3*3大小，我们先双循环遍历矩阵，将石头数量大于1的格子和为0的格子的坐标分别计入到 more 和 less 数组中，方便我们之后的操作；

2. 注意在遍历到大于1的格子的时候，格子中数量为几，说明多出来几个石头，在 more 数组中就应该添加几次。

3. 对于 more 数组中和 less 中记录的下标位置，求解的时候两个格子之间的距离就等于|x1 - x2| + |y1 - y2|。然后只需要遍历找出移动次数最小的即可。

4. 在这里我们用到了一个函数：next_permutation() ，这个函数的意思就是去找寻more的所有可能顺序，如果找到返回 true， 否则返回 false ， 然后在 while 循环中只需要按照找到的可能顺序遍历计算需要操作的步骤即可。

三. 代码

class Solution {
public:
    int minimumMoves(vector<vector<int>>& grid) {
        vector<pair<int, int>> more, less;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(grid[i][j] > 1){
                    for(int k = 2; k <= grid[i][j]; k++){
                        more.push_back({i, j});
                    }
                }else if(grid[i][j] == 0){
                    less.push_back({i, j});
                }
            }
        }
        int ans = INT_MAX;
        sort(more.begin(), more.end());
        bool flag = true;
        while(flag){
            int step = 0;
            for(int i = 0; i < more.size(); i++){
                step += abs(more[i].first - less[i].first) + abs(more[i].second - less[i].second);
            }
            ans = min(ans, step);
            flag = next_permutation(more.begin(), more.end());  // 找到more的所有可能排列
        } 
        return ans;
    }
};

四. 总结

        空间复杂度：记 m, n 分别为矩阵的行数以及列数，则为：O(m*n)；

        这类题目对动态规划以及枚举的要求较高，但也是锻炼思想的一道好题目，建议大家可以练习一下。

喜欢的话给个关注吧！！

原文地址：https://blog.csdn.net/zth12212003/article/details/140572219

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！