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

1.全排列

解题思路：题目难点在于规划哪个石头应该分散到哪个空位上？比如[[1,2,0],[1,0,1],[1,2,1]]这个例子当中，如何保证第三行的2不会分散到第一行的0。

实际上这是一道全局最小问题，局部最小策略(最近的石头分散到最近的空位)得到的结果并不一定是全局最小。也就是说，所有多出的石头和所有空位需要暴力枚举所有可能，才能得到的最优解，因此题目转化为全排列问题。

class Solution {
    int res=Integer.MAX_VALUE;
    public int minimumMoves(int[][] grid) {
        List<int[]> empty=new ArrayList<>();
        List<int[]> stone=new ArrayList<>();
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(grid[i][j]==0){
                    empty.add(new int[]{i,j});
                }
                if(grid[i][j]>1){
                    for(int k=0;k<grid[i][j]-1;k++) 
                        stone.add(new int[]{i,j});
                }
            }
        }
        int[] stonevisit=new int[empty.size()];
        find(empty,stone,stonevisit,0,0);
        return res;
    }
    public void find(List<int[]> empty,List<int[]> stone,int[] stonevisit,int inx,int val){
        if(inx==empty.size()){
            res=Math.min(res,val);
            return;
        }
        int[] emp=empty.get(inx);
        for(int i=0;i<stone.size();i++){
            if(stonevisit[i]==0){
                stonevisit[i]=1;
                int[] sto=stone.get(i);
                int tmp=val+Math.abs(sto[0]-emp[0])+Math.abs(sto[1]-emp[1]);
                find(empty,stone,stonevisit,inx+1,tmp);
                stonevisit[i]=0;
            }
        }
    }
}