题意:给出n,k,其中n可以加1,可以减1,可以乘以2,问至少通过多少次变化使其变成k
可以先画出样例的部分状态空间树
可以知道搜索到的深度即为所需要的最小的变化次数
下面是学习的代码----@_@
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 100005 using namespace std; queue<int> q; int visit[maxn],step[maxn],n,k; int bfs(int n,int k) { int head,next,i; q.push(n); visit[n]=1; step[n]=0; while(!q.empty()) { head=q.front(); q.pop(); for(i=1;i<=3;i++) { if(i==1) next=head-1; else if(i==2) next=head+1; else next=2*head; if(next<=100005&&next>0) { if(!visit[next])//判重 { q.push(next); visit[next]=1; step[next]=step[head]+1; } } if(next==k) return step[next]; } } } int main() { scanf("%d %d",&n,&k); if(n>=k) printf("%d ",n-k); else printf("%d ",bfs(n,k)); }
学习BFS的第一题————go---go--
补写一个模拟队列写的,还是学习的代码,参看的这一篇http://blog.csdn.net/freezhanacmore/article/details/8168265
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 100005 using namespace std; int vis[maxn],n,k; struct node { int x,step; } q[maxn]; int bfs(int n,int k) { node now,next; int head=0,tail=0; q[tail].x=n;//将当前这一节点入队 q[tail].step=0;tail++; vis[n]=1; while(head<tail) { now=q[head];//取出队头 head++;//弹出队头 for(int i=0;i<3;i++) { if(i==0) next.x=now.x+1; else if(i==1) next.x=now.x-1; else next.x=now.x*2; if(next.x<0||next.x>=maxn) continue;//越界了的话就剪枝 if(!vis[next.x]) { vis[next.x]=1; next.step=now.step+1; q[tail]=next; tail++; if(next.x==k) return next.step; } } } } int main() { while(scanf("%d %d",&n,&k)!=EOF) { memset(vis,0,sizeof(vis)); if(n>=k) printf("%d ",n-k); else printf("%d ",bfs(n,k)); } }