poj3278:http://poj.org/problem?id=3278
题意：给你一个n和k，n可以加1也可以减1，还可以乘2，现在要求n经过这样的几步变换可以使得n==k；求得最小的步数。
题解：一开始我也不知道怎么办，准备用深度优先搜，但是自己没打出来，后来看了别人的思路，BFS，马上懂了，就是一个3入口的BFS。裸题。不过要注意0*2的情况。
#include<cstring> #include<cstdio> #include<algorithm> #include<iostream> #include<queue> using namespace std; int n,k; int counts[100002]; struct Node { int x; int step; }; int BFS(int x){ for(int i=0;i<=100000;i++) counts[i]=10000000; counts[x]=0; queue<Node>Q; Node tt; tt.x=x; tt.step=0; Q.push(tt); while(!Q.empty()){ Node temp=Q.front(); Q.pop(); int xx=temp.x; int step=temp.step; if(xx+1<=100000&&step+1<counts[xx+1]){ counts[xx+1]=step+1; Node ttt; ttt.x=xx+1; ttt.step=step+1; Q.push(ttt); } if(xx-1>=0&&step+1<counts[xx-1]){ counts[xx-1]=step+1; Node ttt; ttt.x=xx-1; ttt.step=step+1; Q.push(ttt); } if(xx!=0&&2*xx<=100000&&step+1<counts[xx*2]){//注意这里的xx不等于0的判断 counts[xx*2]=step+1; Node ttt; ttt.x=xx*2; ttt.step=step+1; Q.push(ttt); } } return counts[k]; } int main(){ scanf("%d%d",&n,&k); printf("%d\n",BFS(n)); }