蚱蜢 bfs"/>
蓝桥杯 跳蚱蜢 bfs
有9只盘子,排成1个圆圈。
其中8只盘子内装着8只蚱蜢,有一个是空盘。
我们把这些蚱蜢顺时针编号为 1~8
每只蚱蜢都可以跳到相邻的空盘中,
也可以再用点力,越过一个相邻的蚱蜢跳到空盘中。
请你计算一下,如果要使得蚱蜢们的队形改为按照逆时针排列,
并且保持空盘的位置不变(也就是1-8换位,2-7换位,…),至少要经过多少次跳跃?
注意:要求提交的是一个整数,请不要填写任何多余内容或说明文字。
思路:
不需要得到所有的解,只需要得到最小的解,自然想到bfs,此题目需要判断某点有没有进入过队列,所以设置set进行判断,也可以使用bool数组。
注意bfs数组的出入情况。
#include<bits/stdc++.h>
using namespace std;
struct node {string str;int step;int pos;node (string str,int step,int pos):str(str),pos(pos),step(step){}
};
set <string> vis;
queue <node> q;
void Insert_Inq(node temp,int i)
{string str = temp.str;swap(str[temp.pos],str[(temp.pos+i+9)%9]);if(vis.count(str)==0){vis.insert(str);node n (str,temp.step+1,(temp.pos+i+9)%9);q.push(n);}
}
int main ()
{node first ("012345678",0,0);q.push(first);while (!q.empty()){node temp = q.front();if(temp.str=="087654321"){cout<<temp.step;break;}else {Insert_Inq(temp,1);Insert_Inq(temp,-1);Insert_Inq(temp,2);Insert_Inq(temp,-2);q.pop();}}return 0;
}
更多推荐
蓝桥杯 跳蚱蜢 bfs
发布评论