第八届蓝桥杯省赛C++A组 跳蚱蜢

标题：跳蚱蜢

如图 p1.png 所示：

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

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

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

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

答案：20

思路：这题用的是bfs，蓝桥挺少见bfs的。用一个整型变量来存蚱蜢移动的情况，设空盘为9，那么初始情况就为123456789，终止情况就为876543219。用一个bool数组来判重，比如213456789出现过了，那么下标为213456789的那项记为1。题目说是让蚱蜢跳，我们这里可以向4个方向移动空盘，修改之后的下标对9取模，这样就可以保证他是一个环了。参考的这个：

代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>  
#include<set>
using namespace std;

int s=123456789,t=876543219;
int dir[4]={-2,-1,1,2},a[10]; 
bool index[1000000000];  //index[i]判断情况i是否重复 

int num(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_index;  //记位置情况 
	queue<int>q_step;  //记步数 
	memset(index,0,sizeof(index));
	index[s]=1;
	q_index.push(s);
	q_step.push(1); 
	while(find!=1)
	{
		int x=q_index.front();
		int cnt=q_step.front();
		int k=8,temp;
		while(x>0)
		{
			if(x%10==9)
				temp=k;  //记下空盘的位置 
			a[k--]=x%10;
			x/=10;
		}
		for(int i=0;i<4;i++)
		{
			swap(a[temp],a[(temp+dir[i]+9)%9]);
			int j=num(a);
			if(!index[j])
			{
				if(j==t)
				{
					find=1;
					cout<<cnt<<endl;
				}
				index[j]=1;
				q_index.push(j);
				q_step.push(cnt+1);
			}
			swap(a[temp],a[(temp+dir[i]+9)%9]);
		}
		q_index.pop();
		q_step.pop(); 
	}
}
int main()
{
	bfs();
	return 0;
}