2017年蓝桥杯c++A组第二题 跳蚱蜢

2017年蓝桥杯c++A组第二题 跳蚱蜢

2. 跳蚱蜢

题目描述：
如图所示， 有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。
我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中，也可以再用点
力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变

（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？
输出：输出一个整数表示答案

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <map>
#include <queue>using namespace std;map<string,bool> st;
#define x first
#define y second
string s1;int main()
{string start="012345678";string end = "087654321";queue<pair<string,int>> q;st[start]=true;q.push({start,0}); while(q.size()){auto t=q.front();q.pop();string s=t.x;int d=t.y;cout<<s<<":"<<d<<endl;if(s==end){cout<<d;return 0;}int k=0;for(int i=0;i<9;i++)if(s[i]=='0'){k=i;break;}int m[4];m[0]=(k-1+9)%9;m[1]=(k+1+9)%9;m[2]=(k-2+9)%9;m[3]=(k+2+9)%9;for(int i=0;i<4;i++){s1=s;int t=m[i];swap(s1[k],s1[t]);if(!st[s1]){st[s1]=true;q.push({s1,d+1});} }}return 0;
}

这是一道bfs求最短路径问题，直接找到每种状态的联系方式，建模然后运用bfs()进行求解就行了.