cf 295 div 2 B （bfs）

题意：给出 n、m 两数，可以对 n 进行两种操作 减一或者乘二，操作过程中 n 必须保证非负，问使 n 变为 m 至少需要几步操作。

这是我练水题的时候做到的，题目不难，只是我 bfs 一直没怎么用过比较不熟练，RE 了两发，就整理了这题。

首先，若 n==m ，那么步骤数就是 0 ，而若 n > m ，n 进行乘二的操作就会使 n 离 m 更远，所以必然是一直减一，于是步骤数就是 n -m ；

若 n < m ， 此时由于中间的步骤并不确定，就可以用 bfs 搜索，但是由于使用数组记录某个数字是否被访问过，当数组并没有刻意开很大的时候，就必须先判断对 n 进行操作后的值是否在数组范围内，而不能先判断其数组值，我就因此 RE 了两次，还是需要注意的。

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;

bool f[20005];
int b[20005];

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n>=m)printf("%d
",n-m);
        else{
            memset(f,0,sizeof(f));
            memset(b,0,sizeof(b));
            f[n]=1;
            b[n]=0;
            queue<int>q;
            while(!q.empty()){
                q.pop();
            }
            q.push(n);
            int ans=0;
            while(!q.empty()){
                int a=q.front();
                q.pop();
                if(a<m){
                    if(!f[2*a]){
                        q.push(a*2);
                        f[a*2]=1;
                        b[a*2]=b[a]+1;
                        if(a*2==m){
                            ans=b[a*2];
                            break;
                        }
                    }
                }
                if((a-1)>0){
                    if(!f[a-1]){
                        q.push(a-1);
                        f[a-1]=1;
                        b[a-1]=b[a]+1;
                        if(a-1==m){
                            ans=b[a-1];
                            break;
                        }
                    }
                }
            }
            printf("%d
",ans);
        }
    }
    return 0;
}