leetcode 773. 滑动谜题 DFS

​

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.

一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

示例：

输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成
输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板
输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入：board = [[3,2,4],[1,5,0]]
输出：14
提示：

board 是一个如上所述的 2 x 3 的数组.
board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/sl…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解析：

1、解析最短想到dfs

2、转成字符串

3、数量少 找出可以替换的数组

push queue的时候 向visited add（注意初始化）

/**
 * @param {number[][]} board
 * @return {number}
 */
 var slidingPuzzle = function(board) {
    // 又是最少 dfs
    // 先转成1维数组
    const neighbors = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
    let start = board.flat().join('');
    let queue = [start]; // 转成一维数组
    let visited = new Set();
    visited.add(start)
    let step = 0
    while(queue.length) {
        let cenlength = queue.length;
        console.log('cenlength', cenlength)
        for (let i = 0; i < cenlength; i++) {
            let node = queue.shift();
            if (node == '123450') {
                return step
            }
            let index = node.indexOf("0");
            let adj
            for(let z = 0; z < neighbors[index].length; z++) {
                let new_board = node.split("");
                adj = neighbors[index][z];
                [new_board[index], new_board[adj]] = [new_board[adj], new_board[index]];
                new_board = new_board.join("");
                if (!visited.has(new_board)) {
                    queue.push(new_board);
                    visited.add(new_board);
                }
            }
        }
        step++
    }
    return -1
};
console.log(slidingPuzzle([[1,2,3],[4,0,5]]))
复制代码

（推荐）遍历node时候 向visited add

/**
 * @param {number[][]} board
 * @return {number}
 */
 var slidingPuzzle = function(board) {
    // 又是最少 dfs
    // 先转成1维数组
    const neighbors = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
    let start = board.flat().join('');
    let queue = [start]; // 转成一维数组
    let visited = new Set();
    let step = 0
    while(queue.length) {
        let cenlength = queue.length;
        console.log('cenlength', cenlength)
        for (let i = 0; i < cenlength; i++) {
            let node = queue.shift();
           
            if (node == '123450') {
                return step
            }
            if (visited.has(node)) {
                continue
            }
            visited.add(node);
            let index = node.indexOf("0");
            let adj
            for(let z = 0; z < neighbors[index].length; z++) {
                let new_board = node.split("");
                adj = neighbors[index][z];
                [new_board[index], new_board[adj]] = [new_board[adj], new_board[index]];
                new_board = new_board.join("");
                // if (!visited.has(new_board)) {
                    queue.push(new_board);
                    // visited.add(new_board);
                // }
            }
        }
        step++
    }
    return -1
};
console.log(slidingPuzzle([[1,2,3],[4,0,5]]))
复制代码

参考leetcode-cn.com/problems/sl…

​