BFS题：PIPI的保险箱

客官°小女子只卖身不卖艺 2023-10-06 19:32 35阅读 0赞

## BFS题：PIPI的保险箱 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#### 思路： ####

我们需要找到从起始状态到最终状态的最小操作数，可以使用BFS解决。对于每次操作，我们能旋转9个旋钮中的任一个，即一个状态可以衍生出9个子状态。  
  如何存储9个旋钮的状态？我们可以用一维数组表示9个旋钮的状态，下标对应旋钮，值对应旋钮指示的数字。将该一维数组连同达到该状态花费的操作数一同存入队列中。  
  对于旋钮指示的数字，我们可以将其减1，即0,1，2,3表示题中的1,2，3,4；这样我们能通过加1之后对4取模的方式得到旋转之后指示的数。  
  如何表示标记数组，即如何表示当前状态是否已被访问？或许可以用一个9维数组表示，即vis \[4\] \[4\] \[4\] \[4\] \[4\] \[4\] \[4\] \[4\] \[4\]，若9个旋钮指示的数字为123412341，则vis \[0\] \[1\] \[2\] \[3\] \[0\] \[1\] \[2\] \[3\] \[0\] = 1；不过我们有更好的方式，我们可以用一个4进制数表示状态，比如状态333333330可看成一个4进制数：3 \* 4 ^ 8 + 3 \* 4 ^ 7 + 3 \* 4 ^ 6 + … + 0 \* 4 ^ 0。  
  用一个二维数组relation\[9\] \[4\]表示联动，relation\[i\] \[j\]表示旋钮i在指示j时，对其操作会使relation\[i\] \[j\]号旋钮旋转  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]

**需注意的点** :

*  在bfs时，需弹出队列首元素，之后改变其状态数组的值，设该数组为int\[\] new，在进行9个后续状态的遍历时，需要重新new一个数组，将int\[\] new每个元素的值赋给它。而不能使用int\[\] temp = new，这样temp将成为new的引用，对temp进行修改，原本不想被修改的new也被修改
 *  需注意起始状态就是保险箱开启状态的情况，此时直接输出0

#### 代码： ####

import java.util.*;
    
    public class Main {
        
        static int[] quantity = new int[9];
        static Set<Long> set = new HashSet<>();
        static LinkedList<Node> q = new LinkedList<>();
        static int[][] relation = new int[9][4];
        public static void main(String[] args) {
        
            int i, j;
            quantity[0] = 1;
            for (i = 1;i < 9;i++) {
        
                quantity[i] = quantity[i - 1] * 4;
            }
            Scanner scanner = new Scanner(System.in);
            int[] start = new int[9];
            for (i = 0;i < 9;i++) {
        
                for (j = 0;j < 5;j++) {
        
                    if (j == 0) {
        
                        start[i] = scanner.nextInt() - 1;
                    } else {
        
                        relation[i][j - 1] = scanner.nextInt() - 1;
                    }
                }
            }
            q.add(new Node(start, 0));
            if (cal(start) == 0) {
        
                System.out.println(0);
                return;
            }
            if (!bfs()) {
        
                System.out.println(-1);
            }
        }
    
        static boolean bfs() {
        
            int i;
            long count;
            while (!q.isEmpty()) {
        
                Node now = q.pop();
                for (i = 0;i < 9;i++) {
        
                    int[] temp = new int[9];
                    for (int j = 0;j < 9;j++) {
        
                        temp[j] = now.status[j];
                    }
                    temp[relation[i][temp[i]]] = (temp[relation[i][temp[i]]] + 1) % 4;
                    temp[i] = (temp[i] + 1) % 4;
                    count = cal(temp);
                    if (!set.contains(count)) {
        
                        if (count == 0) {
        
                            System.out.println(now.level + 1);
                            return true;
                        }
                        set.add(count);
                        q.add(new Node(temp, now.level + 1));
                    }
                }
            }
            return false;
        }
    
        static long cal(int[] status) {
        
            long temp = 0;
            for (int i = 0;i < 9;i++) {
        
                temp += status[i] * quantity[i];
            }
            return temp;
        }
    
    }
    
    class Node {
        
        public int[] status;
        public long level;
        public Node(int[] status, long level) {
        
            this.status = status;
            this.level = level;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/5d7a6da99ce54d67949942358689ee59.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/3aa68e3e665948a9a0ae5600c01b0756.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/eca46195fa5a4559bd567aa33d6b6710.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bem6IGM5paw5omL_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/3135f404a9424cc2ade46e7596e59d79.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5bem6IGM5paw5omL,size_20,color_FFFFFF,t_70,g_se,x_16