【leetcode】773. 滑动谜题

leetcode-773.png

最小路径，这种题目一般就需要用BFS来解决了
这一题最最重要的事情就是将题目给建模，建成BFS来解决

搜索.png

由上图可以看到，一个位置可以与另外三个位置来进行交换，然后再进一步的交换，直到找到结果

下面我们要建立一个方便交换的索引对

索引对示意图.png

例如
0这个位置，可以与 1和3进行交换
1可以与 0 2 4 交换
...

BFS

var slidingPuzzle = function (board) {
    // 将目标变成字符串，便于处理
    let start = board.flat().join('')
    let target = '123450'
    // 交换索引
    let swapIndex = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
    let queue = []
    // [当前的滑块组合, 0的位置, 达到这个位置要的步数]
    queue.push([start, start.indexOf('0'), 0])
    // 已经到过的滑块组合
    let visited = new Set([start])
    while (queue.length) {
        let [current, zeroIndex, step] = queue.shift()
        // 找到目标，直接 return
        if (current === target) {
            return step
        }
        // 找到当前 0 能交换的索引数组 swapIndex[zeroIndex]
        for (let index of swapIndex[zeroIndex]) {
            let newBoard = current.split(''); // notice ; 
            // 与相邻的位置进行交换
            [newBoard[zeroIndex], newBoard[index]] = [newBoard[index], newBoard[zeroIndex]]
            let newBoardStr = newBoard.join('')
            // 如果之前没有过这个滑块组合，则进行下一步遍历
            if (!visited.has(newBoardStr)) {
                visited.add(newBoardStr)
                queue.push([newBoardStr, index, step + 1])
            }
        }
    }
    return -1
};

注意这个代码
let newBoard = current.split('');
一定要到后面加分号，不然会报错