题目
原题链接：B. Two Buttons
题意
给定n和m，只能作*2或者-1，求n到m的最少步骤数。标准答案是搜索，也可当规律题。
代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,m;
scanf("%d %d",&n,&m);
int c=0;
if(n>m) {
c=n-m;
} else {
while(n!=m) {
if(m%2==0 && m>n) {
m/=2;
c++;
} else {
if(n>=m){
c+=n-m;
break;
}
m=(m+1)/2;
c+=2;
}
}
}
printf("%d\n",c);
return 0;
}
BFS
#include<stdio.h>
#include<queue>
using namespace std;
struct node {
int value,count;
};
int visit[10010]= {0};
queue<node> q;
int bfs(int n,int m) {
node now,next;
now.count=0;
now.value=n;
while(!q.empty()) q.pop();
q.push(now);
visit[now.value]=1;
while(!q.empty()) {
now=q.front();
q.pop();
if(now.value==m) return now.count;
if(now.value*2<=10000 && !visit[now.value*2]) {
next.value=now.value*2;
next.count=now.count+1;
visit[now.value*2]=1;
q.push(next);
}
if(now.value-1>0 && !visit[now.value-1]){
next.value=now.value-1;
next.count=now.count+1;
visit[now.value-1]=1;
q.push(next);
}
}
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",bfs(n,m));
return 0;
}
