跳蚱蜢(蓝桥杯 )

蚱蜢(蓝桥杯 )"/>

跳蚱蜢(蓝桥杯 )

跳蚱蜢

题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下图所示： 有 9 只盘子，排成 1 个圆圈。 其中 8 只盘子内装着 8 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1 ~ 8。

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

运行限制
最大运行时间：1s
最大运行内存: 128M

算法分析

用数字来存取状态,以9来代表空盘子的位置,其他照常,初始状态为123456789,最终状态为876543219.用一个数组来存储状态,bfs,队列存储pair<int,int>前面代表状态,后面代表当前步数,
交换位置,我们就交换盘子数组,用到状态的话直接转化数字,存入队列当中

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
queue<PII> q;
const int maxn=990000000;
int st=123456789,ed=876543219;
int plate[9];
int dir[4]={-2,-1,1,2};
bool vis[maxn];
int getnum()
{int x=0;for(int i=0;i<9;i++){x=x*10+plate[i];}return x;
}
void bfs()
{q.push(make_pair(st,0));memset(vis,0,sizeof(vis));vis[st]=1;while(q.size()){PII p=q.front();int val=p.first;int step=p.second;q.pop();int jiu;for(int i=8;i>=0;i--){if(val%10==9)jiu=i;plate[i]=val%10;val/=10;}for(int i=0;i<4;i++){swap(plate[jiu],plate[(jiu+dir[i]+9)%9]);int num=getnum();if(!vis[num]){vis[num]=1;if(num==ed){cout<<step+1<<endl;return ;}q.push(make_pair(num,step+1));}swap(plate[jiu],plate[(jiu+dir[i]+9)%9]);}}return ;
}
int main()
{bfs();return 0;
}

最后答案20