JAVA程序设计：滑动谜题（LeetCode：773）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JAVA程序设计：滑动谜题（LeetCode：773），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2000字，纯文字阅读大概需要3分钟。
内容图文
在一个 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] 的排列.
思路：典型可以用广度优先搜索解决的问题，其中我们将用一个6位整数表示board的状态，避免重复遍历。
class Solution {
class node{
int val;
int step;
public node(int val,int step) {
this.val=val;
this.step=step;
}
}
int[] dx= {1,-1,0,0};
int[] dy= {0,0,1,-1};
public int slidingPuzzle(int[][] board) {
Queue<node> q=new LinkedList<>();
boolean[] flag=new boolean[600000];
int start=0;
for(int i=0;i<2;i++)
for(int j=0;j<3;j++)
start=start*10+board[i][j];
q.add(new node(start,0));
flag[start]=true;
while(!q.isEmpty()) {
node now=q.poll();
if(now.val==123450)
return now.step;
int x=0,y=0;
int num1=1,num2=2,tmp=now.val;
while(num1>=0) {
board[num1][num2]=tmp%10;
if(tmp%10==0) {
x=num1; y=num2;
}
tmp/=10;
num2--;
if(num2<0) {
num2=2;
num1--;
}
}
for(int i=0;i<4;i++) {
int xx=x+dx[i];
int yy=y+dy[i];
if(xx<0 || xx>=2 || yy<0 || yy>=3)
continue;
tmp=board[x][y]; board[x][y]=board[xx][yy]; board[xx][yy]=tmp;
int sum=0;
for(int k=0;k<2;k++)
for(int h=0;h<3;h++)
sum=sum*10+board[k][h];
tmp=board[x][y]; board[x][y]=board[xx][yy]; board[xx][yy]=tmp;
if(flag[sum]) continue;
flag[sum]=true;
q.add(new node(sum,now.step+1));
}
}
return -1;
}
}
袁珂晨 发布了1025 篇原创文章 · 获赞 178 · 访问量 22万+ 他的留言板 关注
内容总结
以上是互联网集市为您收集整理的JAVA程序设计：滑动谜题（LeetCode：773）全部内容，希望文章能够帮你解决JAVA程序设计：滑动谜题（LeetCode：773）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。