大佬教程收集整理的这篇文章主要介绍了773. 滑动谜题 力扣(困难) bfs状态改变,写了一个下午,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
题目描述:
在一个 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解释:没有办法完成谜板
题源:https://leetcode-cn.com/problems/sliding-puzzle/
题解:https://michael.blog.csdn.net/article/details/104118648
利用字符串压缩状态,用map作hash,看是否有重复。
学点:
class Solution { public: String vtos(vector<vector<int>> k) { String s; for(int i=0;i<2;i++) for(int j=0;j<3;j++) s.push_BACk(k[i][j]+'0'); // 或者 s=s+to_String(b[i][j]); return s; } void stov(String &s,int &x0,int &y0,vector<vector<int>>& k) { for(int i=0;i<2;i++) for(int j=0;j<3;j++) { k[i][j]=s[i*3+j]-'0'; if( k[i][j]==0 ) { x0=i; y0=j; } // 正确:if (s[i*3+j=='0') 错误:if(s[i*3+j]=="0) } return; } int slidingPuzzle(vector<vector<int>>& board) { int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; map<String,int> mp; bool flag=0; queue<String> Q; String s=vtos(board); Q.push(s); mp[s]=0; while(!Q.empty()) { String p=Q.front(); Q.pop(); int x0,y0; stov(p,x0,y0,board); //得到0点坐标,并且形成矩阵 for(int i=0;i<4;i++) { int x=x0+d[i][0]; int y=y0+d[i][1]; if(!((x>=0 && x<2) && (y>=0 && y<3)) ) conTinue; swap(board[x0][y0],board[x][y]); String s; for(int ii=0;ii<2;ii++) for(int jj=0;jj<3;jj++) s=s+to_String(board[ii][jj]); // 或 s.push_BACk(board[ii][jj]+'0'); if(mp.find(s)==@H_928_46@mp.end()) { mp[s]=mp[p]+1; Q.push(s); } if(s=="123450") {flag=1; break;} swap(board[x0][y0],board[x][y]); } if(flag) break; } if(flag) return mp["123450"]; else return -1; } };
以上是大佬教程为你收集整理的773. 滑动谜题 力扣(困难) bfs状态改变,写了一个下午全部内容,希望文章能够帮你解决773. 滑动谜题 力扣(困难) bfs状态改变,写了一个下午所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。