题目描述
如下图所示： 有 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万，这也是双向广搜的厉害之处。
