1.
#include <bits/stdc++.h> #define N 100001 using namespace std; bool vis[N]; int dir[2]={-1,1}; struct node { int x; int step; }q[N]; void bfs(int n,int k) { int head=1,tail=1; vis[n]=1; q[tail].x=n; q[tail].step=0; tail++; while(head<tail) { int x=q[head].x; int step=q[head].step; if(x==k) { cout<<step; break; } for(int i=0;i<2;i++) { int nx=x+dir[i]; if(1<=nx and nx<=N and vis[nx]==0) { vis[nx]=1; q[tail].x=nx; q[tail].step=step+1; tail++; } } int nx=2*x; if(1<=nx and nx<=N and vis[nx]==0) { vis[nx]=1; q[tail].x=nx; q[tail].step=step+1; tail++; } head++; } } int main() { int n,k; cin>>n>>k; if(k<n) { cout<<n-k; } else { bfs(n,k); } return 0; }
2.
# include <bits/stdc++.h> using namespace std; const int maxN=1e5+1; struct node{ int wz,step; //string s; }; queue<node>Q; int n,k; int vis[2*maxN]; void bfs(int start){ Q.push({start,0}); vis[start]=1; while (!Q.empty()){ int touwz=Q.front().wz; int toustep=Q.front().step; //string tous=Q.front().s; Q.pop(); int newwz[4];//string news[4]; newwz[1]=touwz+1;//news[1]=tous+'A'; newwz[2]=touwz-10;//news[2]=tous+'B'; newwz[3]=touwz*2;//news[3]=tous+'C'; int newstep=toustep+1; for (int i=1;i<=3;i++){ if (newwz[i]==k) { cout<<newstep<<endl;//cout<<news[i]; return; } else if(vis[newwz[i]]==0 && newwz[i]>0 && newwz[i]<=maxN-1) { Q.push({newwz[i],newstep }); vis[newwz[i]]=1; //,news[i] } } } } int main(){ cin>>n>>k; if (n==k) cout<<0<<endl; else bfs(n); return 0; }
注://_____加上后可以输出路径。
标签:头牛,int,step,vis,tail,newwz,news,抓住 From: https://www.cnblogs.com/yjb20090514/p/17574673.html