【蓝桥杯】跳蚱蜢

蚱蜢"/>

【蓝桥杯】跳蚱蜢

跳蚱蜢

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

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

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

思路

• B F S BFS BFS
• 保存每个交换后的状态以及走过的步数，一步一步地进行广搜，直到某个状态符合题意了，就输出步数
• 代码可能复杂了些，而且时间消耗也大，但能算出结果，可能有其它优化，不过填空题就没管那么多，算出答案即可
• 要注意队列和集合中存放字符串时的细节，一定要把字符串复制一遍，而不是直接赋值，那样的话会出错，但是编译器并不会报错，就很烦了

代码如下

#include <cstring>
#include <iostream>
#include <queue>
#include <set>
using namespace std;//初态 0,1,2,3,4,5,6,7,8
//末态 0,8,7,6,5,4,3,2,1//状态类，里面用字符串保存状态，和一个整数表示步数
class Status {public:char* a;int step;//无参构造Status() {a = new char[9];for (int i = 0; i < 9; i++) {a[i] = i + '0';}step = 0;}//复制构造Status(const Status& s) {a = new char[9];for (int i = 0; i < 9; i++) {a[i] = s.a[i];}step = s.step;}//重载=运算符Status operator=(const Status& s) {for (int i = 0; i < 9; i++) {a[i] = s.a[i];}step = s.step;return *this;}//确定空盘(0)的下标int zero_pos() {int pos = 0;for (int i = 0; i < 9; i++) {if (a[i] == '0') {pos = i;break;}}return pos;}//交换两个盘子里的东西，即某一个蚱蜢跳到了附近的空盘void my_swap(int s, int b) {int tmp = a[s];a[s] = a[b];a[b] = tmp;}//判断是否到了需要的状态bool check() { return strcmp(a, "087654321") == 0; }//左边第一个盘子的蚱蜢跳到空盘void sp_l1() {int pos = zero_pos();int lft = (pos - 1 + 9) % 9;my_swap(pos, lft);step++;}//左边第二个盘子的蚱蜢跳到空盘void sp_l2() {int pos = zero_pos();int lft = (pos - 2 + 9) % 9;my_swap(pos, lft);step++;}//右边第一个盘子的蚱蜢跳到空盘void sp_r1() {int pos = zero_pos();int rgt = (pos + 1 + 9) % 9;my_swap(pos, rgt);step++;}//右边第二个盘子的蚱蜢跳到空盘void sp_r2() {int pos = zero_pos();int rgt = (pos + 2 + 9) % 9;my_swap(pos, rgt);step++;}//蚱蜢每跳一次，就相当于状态改变了一下，步数就要加1
};//用于set的比较器，否则set的元素会重复(这是一个坑)
struct cmp {bool operator()(const char* a, const char* b) const {return strcmp(a, b) < 0;}
};queue<Status> q;//bfs的队列
set<char*, cmp> stu;//存储状态的集合，这里为了简单就只存字符串即可void solve() {Status st, top1, top2, top3, top4;//几个临时变量q.push(Status(st));stu.insert(st.a);while (!q.empty()) {//把队列头的元素一分为四，分别对应四种不同的交换top1 = q.front();top2 = q.front();top3 = q.front();top4 = q.front();q.pop();//以下是四种状态的变换top1.sp_l1();if (top1.check()) {//如果发现符合题意了就输出步数，然后直接退出printf("%d\n", top1.step);return;}if (stu.find(top1.a) == stu.end()) {q.push(Status(top1));char* tt = new char[9];strcpy(tt, top1.a);stu.insert(tt);}top2.sp_l2();if (top2.check()) {printf("%d\n", top2.step);return;}if (stu.find(top2.a) == stu.end()) {q.push(Status(top2));char* tt = new char[9];strcpy(tt, top2.a);stu.insert(tt);}top3.sp_r1();if (top3.check()) {printf("%d\n", top3.step);return;}if (stu.find(top3.a) == stu.end()) {q.push(Status(top3));char* tt = new char[9];strcpy(tt, top3.a);stu.insert(tt);}top4.sp_r2();if (top4.check()) {printf("%d\n", top4.step);return;}if (stu.find(top4.a) == stu.end()) {q.push(Status(top4));char* tt = new char[9];strcpy(tt, top4.a);stu.insert(tt);}}
}int main(void) {solve();return 0;
}