滑动谜题 leetcode的BFS题目启发如何写一个拼图编程呢

本文主要是介绍滑动谜题 leetcode的BFS题目启发如何写一个拼图编程呢，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

在这里插入图片描述
题目要求，要将上面的拼板拼成123450

首先，转换为字符串，为什么要转换为字符串呢，因为处理会变得很简单比如示例一，转化为字符串是12345，目标字符串为123450，只需要证明通过某种交换，可不可以得到目标字符串。

那么如何处理交换呢？观察可以发现，假设0在右下角，那么可以向上，和向左交换；假设0在左上角，那么可以向右，向下交换。总结：0在不同的位置，可以有不同的交换方式，我们要把这种交换方式转到字符串处理里面。

如何做到：二维转一维
首先要知道，如何转成字符串，下面是代码：

        string init;//初始字符串for(int i = 0; i < 2; ++i){for(int j = 0; j < 3; ++j){init += char(board[i][j] + '0');//注意}}

board[0][0] 是字符串的第一个（坐标为0）
board[0][1] 是字符串的第二个（坐标为1）
…
board[1][0] 为字符串的四个（坐标是3）
规律为i * 3 + j = 字符串的某个字符的坐标

在这里插入图片描述
上图，是拼板对应字符串的坐标

综上，字符串中，下标为0的字符可以跟下标为1、3的字符交换
下标为1的字符可以跟下标为0、4、2的字符交换
依次类推，可以得到一个数组

vector<vector<int>> dist = {{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};

接下来就是正常的BFS了，找到0字符的位置，通过上面的数组，得到该位置可以跟哪些字符交换，交换，再把这些交换后的字符串，再进行重复操作。查看是否可以得到目标字符串。

class Solution {
public:int slidingPuzzle(vector<vector<int>>& board) {vector<vector<int>> dist = {{1,3},{0,2,4},{1,5},{0,4},{1,3,5},{2,4}};auto get = [&](string status)->vector<string>{//获得从初始字符串，0与其他位置交换后的所有结果vector<string> result;auto pos = status.find('0');//找到字符0的位置for(const auto& nextpos : dist[pos])//获取与0字符相邻的位置，依次交换{swap(status[pos],status[nextpos]);//交换result.push_back(status);//存储新交换的结果swap(status[pos],status[nextpos]);//交换回去，方便下次0字符与其他方向交换}return result;};string init;//初始字符串for(int i = 0; i < 2; ++i){for(int j = 0; j < 3; ++j){init += char(board[i][j] + '0');//注意}}if(init == "123450")//目标字符串{return 0;}unordered_set<string> set = {init};//存储所有交换后的字符串，用来剪枝queue<pair<string,int>> q;//队列，用来BFSq.emplace(init,0);while(!q.empty()){auto [nowStr,nowStep] = q.front();q.pop();for(auto&& newStr : get(nowStr))//遍历下一次交换的结果字符串{if(!set.count(newStr))//剪枝，还没访问过就存入{if(newStr == "123450")//得到目标字符串return nowStep + 1;q.emplace(newStr,nowStep + 1);//注意要先存进去，再下一条语句插入，不然move以后，移动构造，字符串会变为空set.insert(move(newStr));}}}return -1;}
};