标题：跳蚱蜢
如图 p1.png 所示：
有9只盘子，排成1个圆圈。 其中8只盘子内装着8只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1~8
每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？
注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。
答案：20
代码参考了蓝桥学苑老师的思路
#include<iostream> #include<algorithm> #include<cstring> #include<string> #include<set> #include<map> #include<queue> #include<stack> #include<vector> #include<stdlib.h> #include<cmath> #include<stdio.h> #include<windows.h> using namespace std; class AAni{ public: int sp; //空格的位置 int level; //第几步 char* pos; //因为要用strcpy函数，所以使用char*，char*不能直接用等号 AAni(int s, int l, char* p){ pos = (char*)malloc(9); //使用strcpy函数之前要给dest字符数组先分配空间，否则会发生溢出错误 sp = s; level = l; strcpy(pos, p); } }; class cmp{ //给set设置自定义排序 public: bool operator()(const char *a, const char *b)const{ //要加const否则出错，原因还不清楚 return strcmp(a, b) < 0; } }; int d[4] = {1, 2, -1, -2}; //可以跳到空格 void bfs(){ queue<AAni> q; set<char*, cmp> s; //记录是否有重复序列 int i; char des[] = {"012345678"}; //AAni a(0, 0, des); q.push(AAni(0, 0, des)); //可以不用先创建对象直接在push里初始化 s.insert(des); while(!q.empty()){ AAni top = q.front(); q.pop(); if(strcmp(top.pos, "087654321") == 0){ //结束条件 cout << top.level; break; } for(i = 0; i < 4; i++){ int tx = (top.sp + d[i] + 9) % 9; //tx为空格的位置 char* st = (char*)malloc(9); //使用strcpy函数之前要给dest字符数组先分配空间，否则会发生溢出错误 strcpy(st, top.pos); st[top.sp] = st[tx]; //原来空格的地方跳上蚱蜢 st[tx] = '0'; //原来有蚱蜢的地方变成空格 if(!s.count(st)){ //是否出现重复序列，如果没有进行下面操作 s.insert(st); AAni bb(tx, top.level + 1, st); q.push(bb); } } } } int main() { bfs(); return 0; }