BFS 嘛～～
刷了几道搜索水题之后有点感觉了（虽然这题以前在暑假训练计划上出现过
代码很挫，别看，，
题意：从数字n到m，可以通过减一，加一，乘二的方式走，问最短需要几步，很明显的广搜嘛～～
ＡＣ代码：
#include <stdio.h> #include <string.h> #include <algorithm> #include <queue> using namespace std; int n,m,cnt,vis[101101]; struct node { int x; int cnt; }ss; void bfs() { node k; queue<node>q; q.push(ss); vis[ss.x]=1; while(!q.empty()) { node s1=q.front(); q.pop(); k.x=s1.x-1; k.cnt=s1.cnt+1; if(k.x==m) { printf("%d\n",k.cnt); return ; } if(k.x>=0&&k.x<=100000&&vis[k.x]==0) { vis[k.x]=1; q.push(k); } k.x=s1.x+1; k.cnt=s1.cnt+1; if(k.x==m) { printf("%d\n",k.cnt); return ; } if(k.x>=0&&k.x<=100000&&vis[k.x]==0) { vis[k.x]=1; q.push(k); } k.x=s1.x*2; k.cnt=s1.cnt+1; if(k.x==m) { printf("%d\n",k.cnt); return ; } if(k.x>=0&&k.x<=100000&&vis[k.x]==0) { vis[k.x]=1; q.push(k); } } } int main() { while(~scanf("%d%d",&n,&m)) { if(n==m) { printf("0\n"); } else { memset(vis,0,sizeof(vis)); ss.x=n; ss.cnt=0; bfs(); } } return 0; }
原文：http://www.cnblogs.com/qioalu/p/4918511.html