计蒜客bfs密码锁

密码锁

现在一个紧急的任务是打开一个密码锁。密码由四位数字组成，每个数字从到进行编号。每次
可以对任何一位数字加或减。当将 9 加时，数字将变为 1 ，当 1 减的时，数字将变
为 9 。你也可以交换相邻数字，每一个行动记做一步。现在你的任务是使用最小的步骤来打开锁。
注意：最左边的数字不与最右边的数字相邻。

输入格式

第一行输入四位数字，表示密码锁的初始状态。
第二行输入四位数字，表示开锁的密码。

输出格式

输出一个整数，表示最小步骤。

样例输入

1234
2144

样例输出

思路

求解最小问题使用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));
				}
			}
		}
	}
}