Leetcode 2850. Minimum Moves to Spread Stones Over Grid

[Woodyiiiiiii]

2850. Minimum Moves to Spread Stones Over Grid

2850. Minimum Moves to Spread Stones Over Grid

题解：
两种方法：枚举全排列 / 最小费用最大流（Python/Java/C++/Go/JS）

这道题我的想法是BFS，遍历所以超过1的节点，然后通过BFS传递。但这显然会有问题 ，凭什么能保证能最小距离呢？最死板的方法就是遍历所有移动可能，选取最小值。

重点：

1. 遍历所有状态
2. 全排列

class Solution {
    
    public int minimumMoves(int[][] grid) {
        List<int[]> from = new ArrayList<>();
        List<int[]> to = new ArrayList<>();
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 1) {
                    int cnt = grid[i][j];
                    while (cnt-- > 1) {
                        from.add(new int[]{i, j});
                    }
                } else if (grid[i][j] == 0) {
                    to.add(new int[]{i, j});
                }
            }
        }
        
        // get permutations from to list
        List<List<int[]>> perms = new ArrayList<>();
        permute(to, 0, perms);
        
        int min = Integer.MAX_VALUE;
        for (List<int[]> perm : perms) {
            int steps = 0;
            for (int i = 0; i < from.size(); i++) {
                int[] f = from.get(i);
                int[] t = perm.get(i);
                steps += Math.abs(f[0] - t[0]) + Math.abs(f[1] - t[1]);
            }
            min = Math.min(min, steps);
        }
        
        return min;
    }
    
    private void permute(List<int[]> to, int start, List<List<int[]>> perms) {
        if (start == to.size()) {
            perms.add(new ArrayList<>(to));
            return;
        }
        for (int i = start; i < to.size(); i++) {
            swap(to, start, i);
            permute(to, start + 1, perms);
            swap(to, start, i);
        }
    }
    
    private void swap(List<int[]> to, int i, int j) {
        int[] tmp = to.get(i);
        to.set(i, to.get(j));
        to.set(j, tmp);
    }
}

这样的复杂度会是阶乘级别，另一种做法是最小费用最大流。

TODO...