[蓝桥杯2017初赛]跳蚱蜢 BFS

题目描述

如图所示: 有9只盘子,排成1个圆圈。其中8只盘子内装着8只蚱蜢,有一个是空盘。
[蓝桥杯2017初赛]跳蚱蜢 BFS
我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中,也可以再用点力,越过一个相邻的蚱蜢跳到空盘中。
请你计算一下,如果要使得蚱蜢们的队形改为按照逆时针排列,并且保持空盘的位置不变(也就是1-8换位,2-7换位,...),至少要经过多少次跳跃? 

输出

输出一个整数表示答案
 

答案:20

题解

1、用滚动数组表示环,( id+dir[i] +9)%9
 
这份代码跑的巨慢,要5 s ,但是能出答案
#include<iostream>
#include<queue>
#include<algorithm>
#include<set>
using namespace std;
int dir[]={,-,,-};//往 左/右 跳1格或2格
struct node
{
int x;
string s;//保存不同的图,同时用set去标记去重
int cnt;
}A;
int change(string ss)
{
int ans=;
for(int i=;ss[i];i++)
ans=ans*+ss[i]-'';
return ans;
}
void bfs()
{
queue<node>p;
p.push(A);
set<string>se;
se.insert(A.s);
while(!p.empty())
{
node now=p.front();
p.pop();
for(int i=;i<;i++)
{
string ss=now.s;
int tx=now.x+dir[i];
tx=(tx+)%;//滚动数组
//if(ss[tx]=='0')
{
char h=ss[now.x];
ss[now.x]=ss[tx];
ss[tx]=h;
node temp;
temp.x=tx;
temp.s=ss;
temp.cnt=now.cnt+;
if(ss=="")
{
cout<<temp.cnt<<endl;
cout<<temp.s<<endl;
return ;
}
if(se.count(ss)==)//避免往回走,标记状态
{
se.insert(ss);
p.push(temp);
}
}
}
}
}
int main()
{
string str="";//初始状态
//最终状态是 "087654321"
A.x=;
A.s=str;
A.cnt=;
bfs();
return ;
}

文章来源地址https://www.yii666.com/article/754244.html文章地址https://www.yii666.com/article/754244.html网址:yii666.com<网址:yii666.com文章来源地址:https://www.yii666.com/article/754244.html

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png