蓝桥杯之跳蚱蜢

蚱蜢"/>

蓝桥杯之跳蚱蜢

原作：

题目描述：

标题：跳蚱蜢


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


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


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

注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。

思想是bfs广搜，为了节省内存，使用 int 来存储数据，之前用的是string类型以及string类型的数组存放数据，但是太容易超内存，而且判重过程算的太慢，看了这位大神的代码，恍然大悟，可以用 bool 类型的数组进行判重，s = 123456789当作数组下标，以下是我稍作修改的代码，可能看起来更简洁吧！ 

#include <iostream>
#include <queue>
#define Maxn 1000000000using namespace std;int s = 123456789,t = 876543219;int di[4] = {-2,-1,1,2},a[10];bool index[Maxn];int get_val(int *a)
{int sum=0;for(int i=0; i<9; i++){sum*=10;sum+=a[i];}return sum;
}void bfs()
{int find = 0;queue<int> q;queue<char> qu;    //计算步数q.push(s);index[s] = 1;qu.push(1);while(find != 1){int x = q.front(),cnt=8,now;int count = qu.front();while(x>0)    //将数据存入数组，方便换位置{if(x%10==9)now=cnt;a[cnt--]=x%10;x/=10;}for(int i = 0; i<4; i++){swap(a[now],a[(now+di[i]+9)%9]);int num = get_val(a);if(!index[num])  //判重{if(num == t){find = 1;cout<<count;}index[num] = 1;q.push(num);qu.push(count+1);}swap(a[now],a[(now+di[i]+9)%9]);  }q.pop();qu.pop();}}int main()
{bfs();return 0;
}