蓝桥杯 跳蚱蜢【BFS】

蚱蜢【BFS】"/>

蓝桥杯 跳蚱蜢【BFS】

1.题目大意
9个盘子摆成一个环，盘里装着蚱蜢，左四个，右四个，对称轴上有一个空盘，蚱蜢只能跳到相邻的或隔着一个盘子的空盘；开始时顺时针编号（左四个1234，右四个5678）问最少经过多少次跳跃能让盘子编号变为逆时针顺序且开始时的空盘位置不变（左四个8765，右四个4321）

2.解决方法
把当前盘子的状态以字符串形式记录，空盘编号设为0，开始时的状态为123456780，结束状态为876543210。0可以向左或向右移动1，2个单位，从起点BFS直到找到终点；

但是为了复习双向广搜，本题用牛刀杀鸡了，，，，

3.代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>using namespace std;map<string,int> m1;
map<string,int> m2;
int cnt;
string start="123456780";
string ed="876543210";bool extend(queue<string> &q,map<string,int> &m1,map<string,int> &m2)
{string t=q.front();q.pop();string mid=t;int loc;for(int i=0;i<(int)t.size();i++)if(t[i]=='0'){loc=i;break;}for(int i=0;i<4;i++){if(i==0){swap(mid[(loc-2+9)%9],mid[loc]);}else if(i==1){swap(mid[(loc-1+9)%9],mid[loc]);}else if(i==2){swap(mid[(loc+1+9)%9],mid[loc]);}elseswap(mid[(loc+2+9)%9],mid[loc]);if(m2.count(mid)){cout<<m1[t]+1+m2[mid]<<endl;return true;}if(!m1.count(mid)){q.push(mid);m1[mid]=m1[t]+1;}mid=t;}return false;
}void bfs()
{queue<string> q1;queue<string> q2;q1.push(start);q2.push(ed);m1[start]=0;m2[ed]=0;while(!q1.empty()&&!q2.empty()){bool t;if(q1.size()<=q2.size())t=extend(q1,m1,m2);elset=extend(q2,m2,m1);if(t) break;}
}int main(void)
{bfs();return 0;
}