在一个 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)
链接:https://leetcode-cn.com/problems/sliding-puzzle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
?
解析:
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]]))
?