蓝桥杯第642题——跳蚱蜢

题目描述

如下图所示： 有 9 只盘子，排成 1 个圆圈。 其中 8 只盘子内装着 8 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1 ~ 8。

每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1−8 换位，2−7换位，...），至少要经过多少次跳跃？

解题思路

这道题是典型的BFS相关例题，可以练习BFS判重，以及双向广搜的具体方式。

我们从蚱蜢跳跃去考虑并不方便，因为我们每次都有很多只蚱蜢可以进行跳跃，因此我们可以转换思维，考虑到只有一个空盘子，所以第一次跳跃的情况是必定有一只蚱蜢跳到空盘子里；而下一次操作也是同样的情况。

所以我们考虑有哪些蚱蜢可以跳到空盘子上，进一步思考，就是空盘子可以与哪些蚱蜢交换位置，很明显，如图所示，0号空盘可以与2、1、8、7号蚱蜢交换位置，这就为我们提供了搜索路径的灵感；同时，我们是要找到最少的跳跃次数，也就是最短路径，因此我们考虑广度优先搜索。

因为这题不像迷宫，有一个明显的特点，也就是0和2交换的结果——可以由0和1交换，0和2交换，1再和2交换获得。那么这就会导致很多重复，所以后来变换的结果如果与前面已经获取过的结果有重叠，就应当剪枝不再计算，这里我们考虑使用HashSet结构和HashMap结构进行去重。

单点BFS

我们使用一个ArrayDeque构成的队列实现BFS，队列中每个节点的内容是当前的字符串s和得到它所走过的步数step，另外使用一个HashSet来记录搜索过的字符串，很明显先进来的字符串所带来的step数值是最小的，判重过后只需要忽略后续来的相同字符串即可。

以下是常规bfs判重的解题代码：

import java.io.*;
import java.util.*;

public class Main {
    static String S1 = "012345678";
    static String S2 = "087654321";
    static int num = 0;     // 计算队列的操作次数，用于与双向广搜对比
    public static void main(String[] args) throws IOException {
         Set<String> set = new HashSet<>();
         ArrayDeque<Pair> qu = new ArrayDeque<>();
         qu.addLast(new Pair(S1, 0));
         set.add(S1);
         while (!qu.isEmpty()) {
             Pair temp = qu.removeFirst();
             if (temp.s.equals(S2)) {
                 System.out.println(temp.step);
                 System.out.println(num);
                 break;
             }
             // 使用index记录当前字符串中0所在的位置
             int index = 0;
             for (int i = 0; i < 9; i++) {
                 if (temp.s.charAt(i) == '0') {
                     index = i;
                     break;
                 }
             }
             for (int i = index - 2; i <= index + 2; i++) {
                 num++;     // num的每次自增意味着计算的执行次数增加
                 // 使用取余技巧获取将要进行交换的下标
                 int k = (i + 9) % 9;
                 // 5次循环中忽略实际没有交换的情况
                 if (k == index) {
                     continue;
                 }
                 char[] ss = temp.s.toCharArray();
                 char t = ss[k]; ss[k] = ss[index]; ss[index] = t;
                 if (set.add(String.copyValueOf(ss))) {
                     qu.addLast(new Pair(String.copyValueOf(ss), temp.step + 1));
                 }
             }
         }
    }
}

class Pair {
    String s;
    int step;

    public Pair(String s, int step) {
        this.s = s;
        this.step = step;
    }
}

 结果输出中，第一个数值是题目所要求的答案，第二个值代表着该算法的运行次数。

20
1814315

第一种思路的局限性

在考虑单点bfs找最短路径的情况，我们可以想象原点是一颗由上至下的4叉树，那么题目的答案20，意味着我们要向下分出20层才能找到答案，树会不断往底部扩展，越是向下的层数，所需要计算的节点就越是多，如果我们没有去重，想象一个完整的20层4叉树，它是非常巨大的。

那么我们可以考虑另外一种情况，现在我们明确的知道目标结果的字符串，那么我们可以不可以根据最终状态再反向生成一颗树呢？

如果从上至下以及从下至上同时开始广搜，那么我们所需要生成的四叉树就从一个20层的树变成了两个10层的树，同学们可以自行想象，这对时间的节省又是相当巨大的。

双向广搜

在上述单点BFS的基础上，我们进行升级为双向广搜，每次对队列的一次BFS操作都根据队列长度较短的进行选择执行，第一次遇到相同字符串的时候，两个层数加起来就是我们的答案。

我们需要将第一种方式的一个Set修改为两个独立的HashMap，记录字符串出现的同时，也要对应记录其出现的层数，方便我们对答案进行输出。

import java.io.*;
import java.util.*;

public class Main {
    static String S1 = "012345678";
    static String S2 = "087654321";
    static int times = 0;
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        HashMap<String, Integer> map1 = new HashMap<>();
        HashMap<String, Integer> map2 = new HashMap<>();
        ArrayDeque<Pair> qu1 = new ArrayDeque<>();
        ArrayDeque<Pair> qu2 = new ArrayDeque<>();
        qu1.addLast(new Pair(S1, 0));
        map1.put(S1, 0);
        qu2.addLast(new Pair(S2, 0));
        map2.put(S2, 0);

        while (!qu1.isEmpty() && !qu2.isEmpty()) {
            if (qu1.size() < qu2.size()) {
                extend(qu1, map1, map2);
            } else {
                extend(qu2, map2, map1);
            }
            if (ans != 0) {
                System.out.println(ans);
                System.out.println(times);
                break;
            }
        }
    }
    // 注意该方法中的qu是当前操作的队列
    // map对应的是qu的HashMap
    // 而map1是另外一个队列的HashMap
    public static void extend(ArrayDeque<Pair> qu, HashMap<String, Integer> map, HashMap<String, Integer> map1) {
        Pair temp = qu.removeFirst();
        if (map1.containsKey(temp.s)) {
            ans = temp.step + map1.get(temp.s);
            return;
        }
        int index = -1;
        for (int i = 0; i < temp.s.length(); i++) {
            if (temp.s.charAt(i) == '0') {
                index = i;
                break;
            }
        }
        for (int i = index - 2; i <= index + 2; i++) {
            times++;
            int k = (i + temp.s.length()) % temp.s.length();
            if (k == index) {
                continue;
            }
            char[] arr = temp.s.toCharArray();
            char ch = arr[index]; arr[index] = arr[k]; arr[k] = ch;
            String news = String.copyValueOf(arr);
            if (!map.containsKey(news)) {
                map.put(news, temp.step + 1);
                qu.addLast(new Pair(news, temp.step + 1));
            }
        }
    }
}

class Pair {
    String s;
    int step;

    public Pair(String s, int step) {
        this.s = s;
        this.step = step;
    }
}

20
133510

通过两种方法的输出对比我们可以看出，对队列的操作次数由180万降低到了13万，这也是双向广搜的厉害之处。