2 条题解
-
1
202502gj01花子轩 (EL230810) LV 8 @ 1 年前
//深搜可过,但不是最优解
-
02 年前@
- 1
信息
- ID
- 1018
- 难度
- 6
- 分类
- (无)
- 标签
- 递交数
- 110
- 已通过
- 30
- 通过率
- 27%
- 被复制
- 6
- 上传者
#include <bits/stdc++.h>
using namespace std;
int n,k;
int dfs(int k)
{
if(k<=n)
{
return n-k;
}
if(k%2)
{
return min(dfs(k+1)+1,dfs(k-1)+1);
}
else
{
return min(dfs(k/2)+1,k-n);
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k;
int ans=0;
if(n==0)
{
n=1;
ans=1;
}
ans+=dfs(k);
cout<<ans;
return 0;
}
//深搜可过,但不是最优解
#include<iostream>
using namespace std;
int n, k, ans = 0;
int dfs(int k){
if(k <= n)return n-k;
if(k & 1)return min(dfs(k+1), dfs(k-1)) + 1;
else return min(dfs(k/2)+1, k-n);
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> k;
if(n == 0){
n = 1;
ans = 1;
}
cout << dfs(k) + ans;
return 0;
}
#include<algorithm>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000+10;
int n,k;
bool vis[MAXN];
struct Node
{
int x,steps;
Node(int _x,int _steps):x(_x),steps(_steps){};
};
queue<Node> q;
void bfs()
{
q.push(Node(n,0));
vis[n]=true;
while(!q.empty())
{
Node cur=q.front();
q.pop();
int x=cur.x;
if(x==k)
{
cout<<cur.steps<<endl;
break;
}
else for(int i=1;i<=3;++i)
{
int nx;
if(i==1)nx=x-1;
if(i==2)nx=x+1;
if(i==3)nx=x*2;
if(nx>=0&&nx<=100000&&!vis[nx])
{
vis[nx]=true;
q.push(Node(nx,cur.steps+1));
}
}
}
}
int main()
{
memset(vis,false,sizeof(vis));
cin>>n>>k;
if(n==k)
{
cout<<0<<endl;
return 0;
}
bfs();
return 0;
}