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

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

解题思路

见代码注释

code

typedef pair<int,int> PII;

class Solution {
public:
    //数据范围并不算大
    //暴力解
    //移入和移出是一一对应的
    //from : (0,1) (0,1) (2,2) (2,2)
    //to : (0,2) (1,1) (1,2) (2,1)
    //找到from 的全排列

    void dfs(vector<PII> & from,vector<PII> & to,vector<PII> & path,vector<int> & visited,int & ans)
    {
        if(path.size() == from.size())
        {
            int dist = 0;
            for(int i = 0;i < from.size();i++) dist += abs(to[i].first - path[i].first) + abs(to[i].second - path[i].second);
            ans = min(ans,dist);
        }

        for(int i = 0;i < from.size();i ++)
        {
            if(!visited[i])
            {
                path.push_back(from[i]);
                visited[i] = 1;
                dfs(from,to,path,visited,ans);
                path.pop_back();
                visited[i] = 0;
            }
        }
    }

    int minimumMoves(vector<vector<int>>& grid) {

        vector<PII> from;
        vector<PII> to;

        for(int i = 0;i < 3;i ++)
            for(int j = 0;j < 3;j ++)
                if(grid[i][j] == 0)
                    to.push_back({i,j});
                else
                    while(grid[i][j]-- > 1)
                        from.push_back({i,j});
        
        int ans = 0x3f3f3f3f;
        
        vector<PII> path;
        vector<int> visited(from.size(),0);

        dfs(from,to,path,visited,ans);
        
        return ans;
    }
};

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        from_ = []
        to_ = []
        
        for i,row in enumerate(grid):
            for j,cnt in enumerate(row):
                if(cnt > 1):
                    from_.extend([(i,j)] * (cnt - 1))
                elif(cnt == 0):
                    to_.append((i,j))

        ans = inf

        for from2 in permutations(from_):
            total = 0

            for (x1,y1),(x2,y2) in zip(from2,to_):
                total += abs(x1 - x2) + abs(y1 - y2)

            ans = min(ans,total)
        
        return ans