2850. Minimum Moves to Spread Stones Over Grid

source: https://leetcode.com/problems/minimum-moves-to-spread-stones-over-grid/

Question

You are given a 0-indexed 2D integer matrix grid of size 3 * 3, representing the number of stones in each cell. The grid contains exactly 9 stones, and there can be multiple stones in a single cell.

In one move, you can move a single stone from its current cell to any other cell if the two cells share a side.

Return the minimum number of moves required to place one stone in each cell.

Permute

把所有的from位置，和所有的to位置进行全排列后，算出最小的曼哈顿距离。

function permute<T = any>(nums: T[]): T[][] {
    const ret: number[][] = [];
    const dfs = (list: number[], leave: number[]) => {
        if (list.length === nums.length) {
            return ret.push(list);
        }
        leave.forEach(i => {
            dfs([...list, i], leave.filter(v => v !== i));
        });
    };
    dfs([], nums.map((_, i) => i));
    return ret.map(list => list.map(i => nums[i]));
};

function minimumMoves(grid: number[][]): number {
    let ret = Infinity;
    const from = [];
    const to = [];
    grid.forEach((lines, y) => {
        lines.forEach((stones, x) => {
            if (stones !== 1) {
                const position = [y, x] as const;
                if (stones === 0) {
                    to.push(position);
                } else {
                    Array(stones - 1).fill(0).forEach(() => {
                        from.push([...position]);
                    });
                }
            }
        });
    });
    const getLength = (p1: [number, number], p2: [number, number]) => {
        const y = Math.abs(p1[0] - p2[0]);
        const x = Math.abs(p1[1] - p2[1]);
        return y + x;
    };
    permute(from).forEach(f => {
        let total = 0;
        f.forEach((position, i) => {
            total += getLength(position, to[i]);
        });
        ret = Math.min(ret, total);
    });
    return ret;
};

总结

转化为全排列以后，比暴力解法容易写很多。