bfs基础题,每次将x-1,x+1,x*2放入队列,并标记已经访问过的结点,直到找到终点。
注意边界条件
#include <iostream> #include<stdio.h> #include <cstring> #include <algorithm> #include <string.h> #include<queue> const int max_n=100010; using namespace std; int n,k; int mini=max_n; int vis[max_n]; int dis[max_n]; queue<int> q; void update(int x,int y) { q.push(x); dis[x]=dis[y]+1; vis[x]=1; } void bfs(int x) { q.push(x); while(!q.empty()) { int tem=q.front();q.pop(); if(tem==k) { break; } if(vis[tem-1]==0&&tem-1>=0) update(tem-1,tem); if(vis[tem+1]==0&&tem+1<max_n) update(tem+1,tem); if(vis[tem*2]==0&&tem*2<max_n) update(tem*2,tem); } } int main() { cin>>n>>k; memset( dis,0,sizeof(dis) ); memset( vis,0,sizeof(vis) ); bfs(n); cout<<dis[k]<<endl; }