计蒜客bfs密码锁
密码锁
现在一个紧急的任务是打开一个密码锁。密码由四位数字组成,每个数字从 到 进行编号。每次
可以对任何一位数字加 或减 。当将 9 加 时,数字将变为 1 ,当 1 减 的时,数字将变
为 9 。你也可以交换相邻数字,每一个行动记做一步。现在你的任务是使用最小的步骤来打开锁。
注意:最左边的数字不与最右边的数字相邻。
输入格式
第一行输入四位数字,表示密码锁的初始状态。
第二行输入四位数字,表示开锁的密码。
输出格式
输出一个整数,表示最小步骤。
样例输入
1234
2144
样例输出
2
思路
求解最小问题使用bfs进行搜索比dfs更高效,因为使用队列进行层次搜索,在一个层次的步数相同,而后一个层次的步数比前一个层次的步数大一,所以第一个满足条件的就为最小结果。
设置四维数组int[][][][]vis,对每一四位数进行访问标记
循环对对队头元素不同位加1减1或者进行交换,若之前未访问过,将该结点的步数加1,并且加入队尾,直至找到和密码相同的序列,输出退出循环。
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main{
static class Node{
int []num=new int[4];
int ans;
Node(int a,int b,int c,int d,int ans){
this.num[0]=a;
this.num[1]=b;
this.num[2]=c;
this.num[3]=d;
this.ans=ans;
}
Node(){
ans=0;
}
}
static int[][][][] vis=new int[11][11][11][11];
static int add(int a) {
if(a==9) {
a=1;
}else {
a++;
}
return a;
}
static int sub(int a) {
if(a==1) {
a=9;
}else {
a--;
}
return a;
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//StringTokenizer token=new StringTokenizer(br.readLine());
String begin=br.readLine();
String pwd=br.readLine();
Node first=new Node();
Node last=new Node();
for(int i=0;i<4;i++) {
first.num[i]=begin.charAt(i)-'0';
last.num[i]=pwd.charAt(i)-'0';
}
vis[first.num[0]][first.num[1]][first.num[2]][first.num[3]]=1;
Queue<Node> q=new LinkedList<Node>();
Node p;
p=first;
q.add(first);
// int min=0x3f3f3f3f;
while(!q.isEmpty()) {
p=q.poll();
if(p.num[0]==last.num[0]&&p.num[1]==last.num[1]&&p.num[2]==last.num[2]&&p.num[3]==last.num[3]) {
System.out.println(p.ans);
return;
}
for(int i=0;i<4;i++) {
Node next=new Node(p.num[0],p.num[1],p.num[2],p.num[3],p.ans);
next.num[i]=add(next.num[i]);
if(vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]==0) {
vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1;
next.ans++;
q.add(new Node(next.num[0],next.num[1],next.num[2],next.num[3],next.ans));
}
}
for(int i=0;i<4;i++) {
Node next=new Node(p.num[0],p.num[1],p.num[2],p.num[3],p.ans);
next.num[i]=sub(next.num[i]);
if(vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]==0) {
vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1;
next.ans++;
q.add(new Node(next.num[0],next.num[1],next.num[2],next.num[3],next.ans));
}
}
for(int i=0;i<3;i++) {
Node next=new Node(p.num[0],p.num[1],p.num[2],p.num[3],p.ans);
int temp=next.num[i+1];
next.num[i+1]=next.num[i];
next.num[i]=temp;
if(vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]==0) {
vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1;
next.ans++;
q.add(new Node(next.num[0],next.num[1],next.num[2],next.num[3],next.ans));
}
}
}
}
}
结果
注意
需要注意的是Java的引用是动态的,类似于c中的指针,所以如果只是使用Node next=p(代码如下)将p的引用赋值给next后,并且加入队列后,也是一段引用,这一块空间的值仍会变化,使得最后队列中的元素都是同样的序列。
使用dubug调试,队列中的元素如下图