益智游戏克星：BFS暴力搜索算法
滑动拼图游戏大家应该都玩过，下图是一个 4x4 的滑动拼图：
拼图中有一个格子是空的，可以利用这个空着的格子移动其他数字。你需要通过移动这些数字，得到某个特定排列顺序，这样就算赢了。
我小时候还玩过一款叫做「华容道」的益智游戏，也和滑动拼图比较类似：
那么这种游戏怎么玩呢？我记得是有一些套路的，类似于魔方还原公式。但是我们今天不来研究让人头秃的技巧，这些益智游戏通通可以用暴力搜索算法解决，所以今天我们就学以致用，用 bfs 算法框架来秒杀这些游戏。
一、题目解析
leetcode 第 773 题就是滑动拼图问题，题目的意思如下：
给你一个 2x3 的滑动拼图，用一个 2x3 的数组board表示。拼图中有数字 0~5 六个数，其中数字 0 就表示那个空着的格子，你可以移动其中的数字，当board变为[[1,2,3],[4,5,0]]时，赢得游戏。
请你写一个算法，计算赢得游戏需要的最少移动次数，如果不能赢得游戏，返回 -1。
比如说输入的二维数组board = [[4,1,2],[5,0,3]]，算法应该返回 5：
如果输入的是board = [[1,2,3],[4,0,5]]，则算法返回 -1，因为这种局面下无论如何都不能赢得游戏。
二、思路分析
对于这种计算最小步数的问题，我们就要敏感地想到 bfs 算法。
这个题目转化成 bfs 问题是有一些技巧的，我们面临如下问题：
1、一般的 bfs 算法，是从一个起点start开始，向终点target进行寻路，但是拼图问题不是在寻路，而是在不断交换数字，这应该怎么转化成 bfs 算法问题呢？
2、即便这个问题能够转化成 bfs 问题，如何处理起点start和终点target？它们都是数组哎，把数组放进队列，套 bfs 框架，想想就比较麻烦且低效。
首先回答第一个问题，bfs 算法并不只是一个寻路算法，而是一种暴力搜索算法，只要涉及暴力穷举的问题，bfs 就可以用，而且可以最快地找到答案。
你想想计算机怎么解决问题的？哪有那么多奇技淫巧，本质上就是把所有可行解暴力穷举出来，然后从中找到一个最优解罢了。
明白了这个道理，我们的问题就转化成了：如何穷举出board当前局面下可能衍生出的所有局面？这就简单了，看数字 0 的位置呗，和上下左右的数字进行交换就行了：
这样其实就是一个 bfs 问题，每次先找到数字 0，然后和周围的数字进行交换，形成新的局面加入队列…… 当第一次到达target时，就得到了赢得游戏的最少步数。
对于第二个问题，我们这里的board仅仅是 2x3 的二维数组，所以可以压缩成一个一维字符串。其中比较有技巧性的点在于，二维数组有「上下左右」的概念，压缩成一维后，如何得到某一个索引上下左右的索引？
很简单，我们只要手动写出来这个映射就行了：
vectorneighbor={ {1,3}, {0,4,2}, {1,5}, {0,4}, {3,1,5}, {4,2} };
这个含义就是，在一维字符串中，索引i在二维数组中的的相邻索引为neighbor[i]，：
至此，我们就把这个问题完全转化成标准的 bfs 问题了，借助前文bfs 算法框架套路详解的代码框架，直接就可以套出解法代码了：
intslidingpuzzle(vector&board){ intm=2,n=3; stringstart=; stringtarget=123450; //将2x3的数组转化成字符串 for(inti=0;i
至此，这道题目就解决了，其实框架完全没有变，套路都是一样的，我们只是花了比较多的时间将滑动拼图游戏转化成 bfs 算法。
很多益智游戏都是这样，虽然看起来特别巧妙，但都架不住暴力穷举，常用的算法就是回溯算法或者 bfs 算法，感兴趣的话我们以后再聊。
歌尔股份在智能穿戴医疗健康领域取得进一步的突破
美国制造的现实将注定是竹篮打水一场空
纯钧新材料获亿级融资，助推国内温控产业加速崛起
思必驰选择联手强者打造AI芯片 明知山有虎偏向虎山行
机器人成本曲线正在下降 易用性成发展新难题
益智游戏克星：BFS暴力搜索算法
GaN RF市场的主要驱动力仍然是电信和国防应用
智能家居智能社区等智能系统接口防护
中国手机品牌占据非洲市场主导地位,传音在非洲市场份额达到76.6%
盘点可穿戴设备必备核心芯片及主要解决方案
怎样成为一名合格的电子工程师
电路板怎样进行设计和调试
瑞萨电子开发出全新32位微控制器(MCU)V850E2/PJ4-E
适用于汽车和工业场合的高效同步SEPIC控制器
云网融合打造一体化运营服务体系,新一代云网运营呼之欲出
3D打印镜片具有不同折射率，能够用来传递3D光信号
研究人员利用AI技术证实了在可预见的未来，核聚变能量供应的可行性
今日看点丨瑞典要让电动汽车在行驶中充电；小米电致变色镜片专利公布
苹果2020年5G iPhone手机面临的芯片供货商棘手的局面
罗德与施瓦茨展示用于测试卫星有效载荷的新型Q/V波段射频上变频器
拼图中有一个格子是空的，可以利用这个空着的格子移动其他数字。你需要通过移动这些数字，得到某个特定排列顺序，这样就算赢了。
我小时候还玩过一款叫做「华容道」的益智游戏，也和滑动拼图比较类似：
那么这种游戏怎么玩呢？我记得是有一些套路的，类似于魔方还原公式。但是我们今天不来研究让人头秃的技巧，这些益智游戏通通可以用暴力搜索算法解决，所以今天我们就学以致用，用 bfs 算法框架来秒杀这些游戏。
一、题目解析
leetcode 第 773 题就是滑动拼图问题，题目的意思如下：
给你一个 2x3 的滑动拼图，用一个 2x3 的数组board表示。拼图中有数字 0~5 六个数，其中数字 0 就表示那个空着的格子，你可以移动其中的数字，当board变为[[1,2,3],[4,5,0]]时，赢得游戏。
请你写一个算法，计算赢得游戏需要的最少移动次数，如果不能赢得游戏，返回 -1。
比如说输入的二维数组board = [[4,1,2],[5,0,3]]，算法应该返回 5：
如果输入的是board = [[1,2,3],[4,0,5]]，则算法返回 -1，因为这种局面下无论如何都不能赢得游戏。
二、思路分析
对于这种计算最小步数的问题，我们就要敏感地想到 bfs 算法。
这个题目转化成 bfs 问题是有一些技巧的，我们面临如下问题：
1、一般的 bfs 算法，是从一个起点start开始，向终点target进行寻路，但是拼图问题不是在寻路，而是在不断交换数字，这应该怎么转化成 bfs 算法问题呢？
2、即便这个问题能够转化成 bfs 问题，如何处理起点start和终点target？它们都是数组哎，把数组放进队列，套 bfs 框架，想想就比较麻烦且低效。
首先回答第一个问题，bfs 算法并不只是一个寻路算法，而是一种暴力搜索算法，只要涉及暴力穷举的问题，bfs 就可以用，而且可以最快地找到答案。
你想想计算机怎么解决问题的？哪有那么多奇技淫巧，本质上就是把所有可行解暴力穷举出来，然后从中找到一个最优解罢了。
明白了这个道理，我们的问题就转化成了：如何穷举出board当前局面下可能衍生出的所有局面？这就简单了，看数字 0 的位置呗，和上下左右的数字进行交换就行了：
这样其实就是一个 bfs 问题，每次先找到数字 0，然后和周围的数字进行交换，形成新的局面加入队列…… 当第一次到达target时，就得到了赢得游戏的最少步数。
对于第二个问题，我们这里的board仅仅是 2x3 的二维数组，所以可以压缩成一个一维字符串。其中比较有技巧性的点在于，二维数组有「上下左右」的概念，压缩成一维后，如何得到某一个索引上下左右的索引？
很简单，我们只要手动写出来这个映射就行了：
vectorneighbor={ {1,3}, {0,4,2}, {1,5}, {0,4}, {3,1,5}, {4,2} };
这个含义就是，在一维字符串中，索引i在二维数组中的的相邻索引为neighbor[i]，：
至此，我们就把这个问题完全转化成标准的 bfs 问题了，借助前文bfs 算法框架套路详解的代码框架，直接就可以套出解法代码了：
intslidingpuzzle(vector&board){ intm=2,n=3; stringstart=; stringtarget=123450; //将2x3的数组转化成字符串 for(inti=0;i
很多益智游戏都是这样，虽然看起来特别巧妙，但都架不住暴力穷举，常用的算法就是回溯算法或者 bfs 算法，感兴趣的话我们以后再聊。
歌尔股份在智能穿戴医疗健康领域取得进一步的突破
美国制造的现实将注定是竹篮打水一场空
纯钧新材料获亿级融资，助推国内温控产业加速崛起
思必驰选择联手强者打造AI芯片 明知山有虎偏向虎山行
机器人成本曲线正在下降 易用性成发展新难题
益智游戏克星：BFS暴力搜索算法
GaN RF市场的主要驱动力仍然是电信和国防应用
智能家居智能社区等智能系统接口防护
中国手机品牌占据非洲市场主导地位,传音在非洲市场份额达到76.6%
盘点可穿戴设备必备核心芯片及主要解决方案
怎样成为一名合格的电子工程师
电路板怎样进行设计和调试
瑞萨电子开发出全新32位微控制器(MCU)V850E2/PJ4-E
适用于汽车和工业场合的高效同步SEPIC控制器
云网融合打造一体化运营服务体系,新一代云网运营呼之欲出
3D打印镜片具有不同折射率，能够用来传递3D光信号
研究人员利用AI技术证实了在可预见的未来，核聚变能量供应的可行性
今日看点丨瑞典要让电动汽车在行驶中充电；小米电致变色镜片专利公布
苹果2020年5G iPhone手机面临的芯片供货商棘手的局面
罗德与施瓦茨展示用于测试卫星有效载荷的新型Q/V波段射频上变频器