加1乘2平方noj
程序员文章站
2022-06-18 10:06:13
#include#include#include#define MAXN 10000#define true 1#define false 0using namespace std;queueq1;int m,n;int used[MAXN];int step[MAXN];int dfs();int change(int now,int i);int isTarge.....
#include<iostream>
#include<queue>
#include<string.h>
#define MAXN 10000
#define true 1
#define false 0
using namespace std;
queue<int>q1;
int m,n;
int used[MAXN];
int step[MAXN];
int dfs();
int change(int now,int i);
int isTarget(int now,int next);
int main()
{
memset(used,0,sizeof(used));
memset(step,0,sizeof(step));
cin>>m>>n;
q1.push(m);
cout<<dfs()<<endl;
return 0;
}
int dfs()
{
int now,next;
int i;
while(!q1.empty()){
now=q1.front();
q1.pop();
used[now]=1;
for(i=0;i<3;i++){
next=change(now,i);
if(isTarget(now,next)){
return step[next];
}
}
}
}
int change(int now,int i)
{
if(i==0)return (now+1);
if(i==1)return (now*2);
if(i==2)return (now*now);
}
int isTarget(int now,int next)
{
if(next<=n&&!used[next]){
used[next]=1;
step[next]=step[now]+1;
if(next==n)return true;
else{
q1.push(next);
}
}
return false;
}
#include<iostream>
#include<queue>
using namespace std;
queue<int>q1;
int m,n;
int step[10000];//记录到达数字所用的步数
int used[10000];//判断数字是否被用过,即前面步骤中已经得到过
int bfs();//广度优先搜索
int change(int now,int i);//三种变换
bool istarget(int now,int next); //是否到达目标数字
int main()
{
cin>>m>>n;
q1.push(m);
cout<<bfs()<<endl;
return 0;
}
//广度搜索
int bfs()
{
while(!q1.empty())
{
int now=q1.front();//访问队首元素
q1.pop();//出队
used[now]=1;
for(int i=0;i<3;i++)
{
int next=change(now,i);
if(istarget(now,next))
{
return step[next];
}
}
}
}
int change(int now,int i)
{
if(i==0)return now+1;
if(i==1)return now*2;
if(i==2)return now*now;
}
bool istarget(int now,int next)
{
if(next<=n&&!used[next])
{
used[next]=1;
step[next]=step[now]+1;
if(next==n) return true;
else{
q1.push(next);
}
}
return false;
}
本文地址:https://blog.csdn.net/weixin_46112487/article/details/109266598