[蓝桥杯2017初赛]跳蚱蜢

[蓝桥杯2017初赛]跳蚱蜢

如图所示： 有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？
输出一个整数表示答案

思路：把9个盘子，看成一个字符串，空盘子用‘0’来表示，那么开始的字符串start = “012345678”,目标状态end = “087654321”,每一个蚱蜢可以跳到|2|距离的空盘子中去，即四个方向dx[4] = {-2,-1,1,2};
因为所有蚱蜢排成一个圆圈，一个常用的技巧就是使用滚动数组来使盘子可以左右移动：（x + 9） % 9

类似题目：卡片换位 八数码 青蛙跳杯子

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <queue>using namespace std;
int dx[4] = {-2,-1,1,2};
int bfs(string start)
{string end = "087654321"; //目标状态 queue<string> q;unordered_map<string,int> d;q.push(start);d[start] = 0;while (q.size()){auto t = q.front();q.pop();int distance = d[t];if ( t== end)  return distance;int k = t.find('0'); //找到空盘子的下标 for (int i = 0 ;i < 4 ; i ++) //遍历四个方向 {int a = (k + dx[i] + 9) % 9;  if (a >=0 && a <= 8){swap(t[k],t[a]);if (!d.count(t)) //判断这个状态是否出现过 {d[t] = distance + 1;q.push(t);}swap(t[k],t[a]);}}}
}
int main()
{string start = "012345678"; //起始状态 cout << bfs(start) << endl;return 0;
}