计蒜客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));
				}
			}
		}
	}
}

结果

计蒜客bfs密码锁

注意

需要注意的是Java的引用是动态的,类似于c中的指针,所以如果只是使用Node next=p(代码如下)将p的引用赋值给next后,并且加入队列后,也是一段引用,这一块空间的值仍会变化,使得最后队列中的元素都是同样的序列。
计蒜客bfs密码锁
使用dubug调试,队列中的元素如下图
计蒜客bfs密码锁

计蒜客bfs密码锁