bfs 跳蚱蜢

蚱蜢"/>

bfs 跳蚱蜢

题目链接: .php?id=1318

有9只盘子，排成1个圆圈。

其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8

每只蚱蜢都可以跳到相邻的空盘中，

也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，

并且保持空盘的位置不变（也就是1-8换位，2-7换位,…），至少要经过多少次跳跃？
注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。
//青蛙跳格子，我采用裸广搜的方法，几秒可以出答案，但是有时间限制就不行了

//将青蛙跳看作是，圆盘跳动，这样就只有一个变量在变化了

//将圆盘看成是0,初始序列用012345678表示，在广搜的时候用set判一下重

#include <iostream>
#include <queue>
#include <set>
using namespace std;set<string>vis;
struct node
{string str;int step;int pos;node(string str,int step,int pos):str(str),step(step),pos(pos){}
};
queue<node>q;
int dir[]={1,-1,2,-2};
void bfs(node start)
{q.push(start);while(!q.empty()){node nw=q.front();if(nw.str=="087654321"){cout<<nw.step<<endl;return ;}else{for(int i=0;i<4;i++){string s=nw.str;swap(s[nw.pos],s[(nw.pos+dir[i]+9)%9]);if(vis.count(s)==0){vis.insert(s);node now(s,nw.step+1,(nw.pos+dir[i]+9)%9);q.push(now);}}q.pop();}}
}
int main(int argc, char const *argv[])
{string str="012345678";node start(str,0,0);bfs(start);return 0;
}

代码解释

#include<bits/stdc++.h>
using namespace std;
struct node
{string str;//局面字符串int pos;//0的位置也就是空盘子int step;//到达这个局面的步数node(string str,int pos,int step):str(str),pos(pos),step(step) {}
};
int N=9;
set<string> visited;//已经搜索过的局面
queue<node> q;//用户来广搜的队列
void insertq(node no,int i)//node为新的局面,i为移动方式
{string s=no.str;swap(s[no.pos],s[(no.pos+i+9)%9]);//将0和目标位置数字交换//取模是为了模拟循环的数组if(visited.count(s)==0)//如果没有搜索过这个局面{visited.insert(s);node n(s,(no.pos+i+9)%9,no.step+1);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{//四种跳法insertq(temp,1);insertq(temp,-1);insertq(temp,2);insertq(temp,-2);q.pop();}}
}

类似题目 青蛙跳杯子

青蛙跳杯子 ： .html

代码

#include <iostream>
#include <queue>
#include <set>
using namespace std;struct node
{string str;int pos;int step;node(string str,int pos,int step):str(str),pos(pos),step(step){}
};
queue<node>q;
set<string>vis;
string s1,s2;
int dir[]={1,-1,2,-2,3,-3};
void bfs(node start)
{q.push(start);while(!q.empty()){node now=q.front();if(now.str==s2){cout<<now.step<<endl;return;}for(int i=0;i<6;i++){string s=now.str;int n=now.pos+dir[i];if(n<0||n>=s.length())continue;swap(s[now.pos],s[n]);if(vis.count(s)==0){vis.insert(s);node nw(s,n,now.step+1);q.push(nw);}}q.pop();}
}
int main(int argc, char const *argv[])
{int k;cin>>s1>>s2;for(int i=0;i<s1.length();i++){if(s1[i]=='*'){k=i;break;}}node start(s1,k,0);bfs(start);return 0;
}