09-10 20:27 南京林业大学 算法工程师 发布于江苏
关注
例题9.1 Catch That Cow
//个人感觉BFS挺简单的，就调用一个函数就行
#include
#include
#include//memset
using namespace std;
struct Pos
{
int pos;
int t;
Pos(int pos,int t):pos(pos),t(t){}
};
bool visit[100000];
void BFS(int n,int k)
{
queue q;
Pos current(n,0);
q.push(current);
visit[n]=true;
while(!q.empty())
{
Pos cur=q.front();
q.pop();
if(cur.pos==k){
cout<
}
for(int i=1;i<=3;i++)
{
Pos nextpos(0,0);//必须要初始化
if(i==1){
nextpos.pos=cur.pos-1;
nextpos.t=cur.t+1;
}
else if(i==2){
nextpos.pos=cur.pos+1;
nextpos.t=cur.t+1;
}
else
{
nextpos.pos=cur.pos*2;
nextpos.t=cur.t+1;
}
if(nextpos.pos<0||nextpos.pos>100000||visit[nextpos.pos]==true)
{
continue;
}
q.push(nextpos);
visit[nextpos.pos]=true;
}
}
}
int main()
{
int m;cin>>m;
int n,k;
for(int i=1;i<=m;i++)
{
cin>>n>>k;
memset(visit,false,sizeof(visit));
BFS(n,k);
}
}
#include
#include
#include
using namespace std;
struct Pos
{
int pos;
int t;
Pos(int pos,int t):pos(pos),t(t){}
};
bool visit[100000];
void BFS(int n,int k)
{
queue
Pos current(n,0);
q.push(current);
visit[n]=true;
while(!q.empty())
{
Pos cur=q.front();
q.pop();
if(cur.pos==k){
cout<
}
for(int i=1;i<=3;i++)
{
Pos nextpos(0,0);//必须要初始化
if(i==1){
nextpos.pos=cur.pos-1;
nextpos.t=cur.t+1;
}
else if(i==2){
nextpos.pos=cur.pos+1;
nextpos.t=cur.t+1;
}
else
{
nextpos.pos=cur.pos*2;
nextpos.t=cur.t+1;
}
if(nextpos.pos<0||nextpos.pos>100000||visit[nextpos.pos]==true)
{
continue;
}
q.push(nextpos);
visit[nextpos.pos]=true;
}
}
}
int main()
{
int m;cin>>m;
int n,k;
for(int i=1;i<=m;i++)
{
cin>>n>>k;
memset(visit,false,sizeof(visit));
BFS(n,k);
}
}
全部评论
相关推荐
点赞 评论 收藏
分享
叮咚买菜公司氛围 13人发布
查看2道真题和解析
投递华为等公司10个岗位 > 点赞 评论 收藏
分享