BFS——练习题——密码锁

基本模型

void bfs() {    // 传入起始点
    // 1.将起始点放入队列中
    
    // 2.标记起点访问
    
    while() {   // 如果队列不为空
        // 3.访问队列中队首元素x
        
        // 4.删除队首元素
        
        for(){  // 遍历x所有相邻点
            if() {  // 如果该点未被访问过且合法   
                // 5.将该点加入队列末尾
            }
        }
    }
}

练习题

1.密码锁

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

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

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

输入样例：
1234
2144

输出样例：
2

思路：

首先处理输入和初始化队列，以Node类模拟一个四位数数字，分别列出三种情况（加1、减1、交换相邻两个数），然后循环取出队列首元素判断是否满足退出条件，不满足则进行三种情况的操作。
第一种情况是：将取出来的队首元素的每个数字进行加1，然后逐个放入到队列中去，注意第一个for循环下来，共有四个Node被放到队列中去，且每个Node的step都是一样的（都为1）
比如：1234，取出1234这个Node，克隆一份，加1就是2234（step=1）放入队列中，接着再克隆一份1234这个Node，再加1就是1334，以此类推。（每次都在1234的基础上加1，只不过加的位数不同），所以对1234进行加1的操作产生的队列是就2234 1334 1244 1235（step都为1）。
其他情况类似。

注意：如果Node next = now；则next保存的是now的引用，修改next同时也修改了now，因此需要使用java的深克隆（Node类中的含有数组）

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 计蒜客——密码锁
 * @author 无处安身
 *
 */
public class Main {

    public static void main(String[] args) throws CloneNotSupportedException {
        
        Scanner sc = new Scanner(System.in);
        
        char[] arr1 = sc.nextLine().toCharArray();
        char[] arr2 = sc.nextLine().toCharArray();
        
        
        Node first = new Node();    // 密码锁初始状态
        Node last = new Node();     // 开锁的密码
        
        for(int i = 0; i < 4; i++) {
            first.num[i] = arr1[i] - '0';
            last.num[i] = arr2[i] - '0';
        }
        
        int[][][][] vis = new int[11][11][11][11];
        Queue<Node> queue = new LinkedList<Node>();
        
        queue.add(first);
        vis[first.num[0]][first.num[1]][first.num[2]][first.num[3]] = 1;
        
        while(!queue.isEmpty()) {
            Node now = queue.poll();
            
            // 如果找到了开锁的密码就退出
            if(isKey(now, last)) {
                System.out.println(now.step);
                return;
            }

            // 加1的情况
            for (int i = 0; i < 4; i++) {               
                Node next = (Node) now.clone();
                next.num[i]++;
                if(next.num[i] == 9) 
                    next.num[i] = 1;
                
                if(check(next, vis)) {
                    vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
                    next.step++;
                    queue.add((Node) next.clone());
                }
            }
            
            // 减1的情况
            for (int i = 0; i < 4; i++) {
                Node next = (Node) now.clone();
                next.num[i]++;
                if(next.num[i] == 1) 
                    next.num[i] = 9;
                
                if(check(next, vis)) {
                    vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
                    next.step++;
                    queue.add((Node) next.clone());
                }
            }
            
            // 交换2个数的情况
            for(int i = 0; i < 3; i++) {
                Node next = (Node) now.clone();
                int temp=next.num[i+1];
                next.num[i+1]=next.num[i];
                next.num[i]=temp;
                
                if(check(next, vis)) {
                    vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] = 1;
                    next.step++;
                    queue.add((Node) next.clone());
                }
            }
        }       
    }

    
    // 检查这个四位数是否访问过
    public static boolean check(Node next, int[][][][] vis) {
        
        return vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]] == 0;
    }
    

    // 检查是不是开锁的密码
    public static boolean isKey(Node now, Node last) {
        
        return now.num[0] == last.num[0] && now.num[1] == last.num[1] && 
                now.num[2] == last.num[2] && now.num[3] == last.num[3];
    }
    
    static class Node implements Cloneable {
        int[] num = new int[4];
        int step = 0;
        
        Node() {
            
        }
        
        Node(int a,int b,int c,int d,int step){
            this.num[0]=a;
            this.num[1]=b;
            this.num[2]=c;
            this.num[3]=d;
            this.step=step;
        }
        
        @Override
        protected Object clone() throws CloneNotSupportedException {
            Node node = (Node) super.clone();
            node.num = new int[4];
            System.arraycopy(this.num, 0, node.num, 0, 4);
            
            return node;
        }
    }
}