算法学习：滑动谜题

当前位置:

首页 > temp > JavaScript教程 >

算法学习：滑动谜题

今天在力扣看到一道题，顺手写了下，这里记录一下思路。

题目名称：滑动谜题

在一个 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 步完成<br>

									输入：board = [[1,2,3],[5,4,0]]

									输出：-1

									解释：没有办法完成谜板<br>

									输入：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]]<br>

									输入：board = [[3,2,4],[1,5,0]]

									输出：14

解题思路

广度优先搜索树，很暴力。模拟正常的操作，每次把滑块挪到邻接的格子里，然后储存滑板状态。直到找到目标值，或者把滑板的状态穷举完

【执行结果】：执行用时：83.78%; 内存消耗：100%

代码如下：

			
									var slidingPuzzle = function(board) {

									    let target = [1, 2, 3, 4, 5, 0]

									    // 邻接数组，滑板板上面每个位置可以移动的方位

									    let neighbor = [[3, 1], [4, 0, 2], [5, 1], [0, 4], [1, 3, 5], [2, 4]]

									    // 移动状态数组，储存当次移动和下次移动的移动状态。

									    // 数组前面储存当次未遍历状态，后面储存下次将要遍历的状态

									    let queue = [[].concat(...board)]

									    let visited = {}, step = 0

									    while (queue.length) {

									        // queue长度会发生变化，这里len需要事先储存

									        let len = queue.length

									        // 依次将当前步数状态转化为下一步的状态，

									        while (len--) {

									            const cur = queue.shift();

									            if (cur.toString() === target.toString()) return step

									            let idx = cur.findIndex(v => !v)

									            // 依次从邻接数组移动滑块至空位

									            for (let j = 0; j < neighbor[idx].length; j++) {

									                let adj = neighbor[idx][j]

									                let list = [...cur];

									                // 移动滑块，交换位置，表示已移动

									                [list[adj],list[idx]] = [list[idx],list[adj]]

									                // 新状态添加进移动状态数组，准备下次移动

									                if(!visited[list.toString()]){

									                    queue.push(list)

									                    visited[list.toString()] = true

									                }

									            }

									        }

									        // 循环结束表明所有状态均已转换至下一步，此时步数加一，开始循环下一步

									        step++

									    }

									    return -1

									};

__EOF__

本文作者：林恒

本文链接： https://www.cnblogs.com/smileZAZ/p/14825815.html

栏目列表