Various Tree（BFS）
链接：https://www.nowcoder.com/acm/contest/106/J
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
It’s universally acknowledged that there’re innumerable trees in the campus of HUST.
And there are many different types of trees in HUST, each of which has a number represent its type. The doctors of biology in HUST find 4 different ways to change the tree’s type x into a new type y:
1. y=x+1
2. y=x-1
3. y=x+f(x)
4. y=x-f(x)
The function f(x) is defined as the number of 1 in x in binary representation. For example, f(1)=1, f(2)=1, f(3)=2, f(10)=2.
Now the doctors are given a tree of the type A. The doctors want to change its type into B. Because each step will cost a huge amount of money, you need to help them figure out the minimum steps to change the type of the tree into B.
Remember the type number should always be a natural number (0 included).
输入描述:
One line with two integers A and B, the init type and the target type.
输出描述:
You need to print a integer representing the minimum steps.
从a变化到b ~最短的路径是多少~bfs一下就好
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
bool vis[1500005];
struct ***
{
int data;
int step;
};
int erj(int x)
{
int l=25;
int ans=0;
while(l>=0)
{
if((1<<l)&x)
{
ans++;
}
l--;
}
return ans;
}
int f(int x,int nu)
{
if(nu==1)
{
return x+1;
}
else if(nu==2)
{
return x-1;
}
else if(nu==3)
{
return x+erj(x);
}
return x-erj(x);
}
int bfs(int st,int en)
{
queue<***>q;
*** sta;
sta.data=st;sta.step=0;
q.push(sta);
vis[st]=1;
while(!q.empty())
{
*** t=q.front();
if(t.data==en)
{
return t.step;
break;
}
q.pop();
for(int s=1;s<=4;s++)
{
int tm=f(t.data,s);
if(tm>=0&&tm<=1500000&&!vis[tm])
{
*** tem;
tem.data=tm;tem.step=t.step+1;
q.push(tem);
vis[tm]=1;
}
}
}
return -1;
}
int main()
{
int a,b;
while(~scanf("%d%d",&a,&b))
{
memset(vis,0,sizeof(vis));
int ans=bfs(a,b);
printf("%d\n",ans);
}
return 0;
}
大疆公司氛围 168人发布
