HDOJ 2717 Catch That Cow (BFS)

題意：從N到K有3中走法：坐標加1、減1、乘2。求從N到K的最短步數。
思路：BFS
[cpp] 
#include<cstdio> 
#include<cstring> 
#include<queue> 
using namespace std; 
 
int n,k,cnt[111111]; 
 
void bfs() 
{ 
    queue <int> q; 
    q.push(n); 
    cnt[n]=0; 
    while(!q.empty()) 
    { 
        int now=q.front(); 
        q.pop(); 
        if(k==now) 
            break; 
        int next=now+1; 
        if(!cnt[next]) 
        { 
            q.push(next); 
            cnt[next]=cnt[now]+1; 
        } 
        next=now-1; 
        if(next>=0&&!cnt[next]) 
        { 
            q.push(next); 
            cnt[next]=cnt[now]+1; 
        } 
        next=2*now; 
        if(next<=100000&&!cnt[next]&&next-k<k-now) 
        { 
            q.push(next); 
            cnt[next]=cnt[now]+1; 
        } 
    } 
} www.2cto.com
 
int main() 
{ 
    while(scanf("%d%d",&n,&k)==2) 
    { 
        memset(cnt,0,sizeof(cnt)); 
        if(n>=k) 
            cnt[k]=n-k; 
        else 
            bfs(); 
        printf("%d\n",cnt[k]); 
    } 
    return 0; 
} 

作者：sdc1992