题目

原题链接：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;
}