密码锁现在一个紧急的任务是打开一个密码锁。密码由四位数字组成，每个数字从 到 进行编号。每次 可以对任何一位数字加 或减 。当将 9 加 时，数字将变为 1 ，当 1 减 的时，数字将变 为 9 。你也可以交换相邻数字，每一个行动记做一步。现在你的任务是使用最小的步骤来打开锁。 注意：最左边的数字不与最右边的数字相邻。 输入格式第一行输入四位数字，表示密码锁的初始状态。 第二行输入四位数字，表示开锁的密码。 输出格式输出一个整数，表示最小步骤。测试数据： 1234 2144 答案：2 1234 5687 答案：13 package 广度优先搜索; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class 密码锁 { static class Node{ int []num=new int [4]; int step; Node() {} Node (int a,int b,int c,int d){ num[0]=a; num[1]=b; num[2]=c; num[3]=d; } } static Node first=new Node(); static Node last=new Node(); static int[][][][] vis=new int[11][11][11][11]; static void bfs() { int i; Node a=new Node(); Queue q=new LinkedList(); a=first; //a指向first a改变first也要跟着改变 a.step=0; //起始步数要清为0 q.offer(a); //vis数组表示搜没搜到这个状态 vis[a.num[0]][a.num[1]][a.num[2]][a.num[3]]=1; while(!q.isEmpty()) { a=q.peek(); //当前的状态 q.poll(); //bfs出口 if(a.num[0]==last.num[0]&&a.num[1]==last.num[1]&&a.num[2]==last.num[2]&&a.num[3]==last.num[3]){ System.out.println(a.step); return; } //下一步状态for(i=0; i<4; i++) {//+1 Node next=new Node(a.num[0],a.num[1],a.num[2],a.num[3]); next.num[i]++; if(next.num[i]==10) { next.num[i]=1; } if(vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]!=1) { vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1; next.step=a.step+1; q.offer(next); } } for(i=0; i<4; i++) {//-1 System.out.println(a.num[0]+""+a.num[1]+""+a.num[2]+""+a.num[3]); Node next=new Node(a.num[0],a.num[1],a.num[2],a.num[3]); next.num[i]--; if(next.num[i]==0) { next.num[i]=9; } System.out.println(next.num[0]+""+next.num[1]+""+next.num[2]+""+next.num[3]); if(vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]!=1) { vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1; next.step=a.step+1; q.offer(next); } } for(i=0; i<3; i++) { Node next=new Node(a.num[0],a.num[1],a.num[2],a.num[3]); int temp=next.num[i]; next.num[i]=next.num[i+1]; next.num[i+1]=temp; if(vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]!=1) { vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1; next.step=a.step+1; q.offer(next); } } } } public static void main(String[] args) { Scanner reader=new Scanner(System.in); String init=reader.next(); String password=reader.next(); for(int i=0; i<4; i++) { first.num[i]=init.charAt(i)-'0'; last.num[i]=password.charAt(i)-'0'; } bfs(); }}

package 广度优先搜索; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class 打水滴 { static class Node{//记录格子的状态 int x,y,pos,tm; Node(int _x,int _y,int p,int t){ x=_x; y=_y; tm=t; pos=t; } Node(){} } static int n,m,L,q; static boolean[][] vis; static int[][] sum; static int [][]tm; //记录时间 //上 左 下 右 static int[][] dir= {{-1,0},{0,-1},{1,0},{0,1}}; static void bfs(int x,int y) { Queue q=new LinkedList(); Node cur=new Node(); //该位置加上水滴 sum[x][y]++; if(sum[x][y]>L) {//x,y这个网格水滴数大于L for(int i=0; i<4; i++) { //结点记录网格位置 水滴破裂的时间和飞出方向 cur.x=x; cur.y=y; cur.pos=i; cur.tm=0; q.offer(cur); //压入队列 } //该网格水滴置为0时间为0 sum[x][y]=0; tm[x][y]=0; } //搜索 while(!q.isEmpty()) { cur=q.poll(); int xx=cur.x+dir[cur.pos][0]; int yy=cur.y+dir[cur.pos][1]; int ttm=cur.tm; if(xx<0||xx>=n||yy<0||yy>=m) { continue; } //再ttm+1秒破灭过 处理同一秒多个水滴进入一个格子 if(tm[xx][yy]==ttm+1) { continue; }else if(sum[xx][yy]>0){ sum[xx][yy]++; if(sum[xx][yy]>L) { sum[xx][yy]=0; tm[xx][yy]=ttm+1; for(int i=0; i<4; i++) { Node temp=new Node(); temp.x=xx; temp.y=yy; temp.pos=i; temp.tm=ttm+1; q.offer(temp); } } }else { //该网格水滴为0 记录时间和要传递的方向 Node temp=new Node(); temp.x=xx; temp.y=yy; temp.pos=cur.pos; temp.tm=ttm+1; q.offer(temp); }} } public static void main(String[] args) { Scanner reader=new Scanner(System.in); n=reader.nextInt(); m=reader.nextInt(); L=reader.nextInt(); vis=new boolean[n][m]; sum=new int[n][m]; tm=new int[n][m]; //网格 for(int i=0; i