p2p网贷网站建设哪家好,做期货浏览哪些网站,在线外链发布工具,wordpress 修改标题1. 题目
在一个 2 x 3 的板上#xff08;board#xff09;有 5 块砖瓦#xff0c;用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字#xff08;上下左右#xff09;进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开…1. 题目
在一个 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. BFS解题 类似于上图的拼图游戏问到达某一状态的最小移动步数。
类似题目LeetCode 1284. 转化为全零矩阵的最少反转次数BFS 矩阵状态编码解码
BFS队列push地图的初始状态将队列里的状态取出还原地图按着几个方向移动0生成的新的状态push进队列
class Solution {vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};int m, n, i, j, k, step 0, size, x, y;
public:int slidingPuzzle(vectorvectorint board) {m board.size(), n board[0].size();string ans 123450, state;int x0, y0, xi, yi;pairint,int xy0;//0的坐标queuestring q;unordered_setstring visited;//访问标记集合state boardToString(board);//初始状态if(state ans)return step;q.push(state);visited.insert(state);while(!q.empty()){step;size q.size();while(size--){xy0 stringToBoard(q.front(), board);//还原地图并得到0的坐标q.pop();x0 xy0.first;y0 xy0.second;for(k 0; k 4; k){ //0可以4个方向交换xi x0dir[k][0];yi y0dir[k][1];if(xi0 xim yi0 yin){swap(board[xi][yi], board[x0][y0]);//交换state boardToString(board);//新的状态if(state ans)return step;if(!visited.count(state))//没有出现过该地图{visited.insert(state);q.push(state);}swap(board[xi][yi], board[x0][y0]);//还原现场}}}}return -1;}string boardToString(vectorvectorint board) { //地图转成字符串string s;for (i 0; i m; i)for(j 0; j n; j)s.push_back(board[i][j]0);return s;}pairint,int stringToBoard(string s, vectorvectorint board){ //字符串还原成地图并return 0的坐标方便下次挪动for (i m-1; i 0; i--)for(j n-1; j 0; j--){board[i][j] s.back()-0;s.pop_back();if(board[i][j] 0)x i, y j;}return make_pair(x, y);}
};
