4 条题解
-
3
#include<bits/stdc++.h> using namespace std; int n,k; struct id { int x,s; }; const int N=1e5; queue<id>q; bool qp[N+5]; int main() { memset(qp,true,sizeof(qp)); cin>>n>>k; q.push(id{n,0}); qp[n]=false; while(!q.empty()) { id t=q.front(); q.pop(); if(t.x+1==k||t.x-1==k||t.x*2==k) { cout<<t.s+1; return 0; } if(t.x+1<=N&&qp[t.x+1]) { q.push(id{t.x+1,t.s+1}); qp[t.x+1]=false; } if(t.x*2<=N&&qp[t.x*2]) { q.push(id{t.x*2,t.s+1}); qp[t.x*2]=false; } if(t.x-1>=0&&qp[t.x-1]) { q.push(id{t.x-1,t.s+1}); qp[t.x-1]=false; } } return 0; }
-
1
#include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <cwchar> #include <cwctype> #include <complex.h> #include <deque> #include <exception> #include <fstream> #include <functional> #include <fenv.h> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <inttypes.h> #include <limits> #include <list> #include <map> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <stdbool.h> #include <stdint.h> #include <tgmath.h> #include <utility> #include <vector> using namespace std; #define LL long long const int N = 2e5 + 10; const int INF = 0x3f3f3f3f; struct node{ int pos , step; }; int n , k; bool v[N]; void bfs(int x){ queue<node> q; q.push((node){x , 0}); v[x] = 1; while(!q.empty()){ node top = q.front(); q.pop(); if(top.pos == k){ cout << top.step; exit(0); } if(top.pos + 1 <= 200000 && !v[top.pos + 1]){ v[top.pos + 1] = 1; q.push((node){top.pos + 1 , top.step + 1}); } if(top.pos - 1 >= 0 && !v[top.pos - 1]){ v[top.pos - 1] = 1; q.push((node){top.pos - 1 , top.step + 1}); } if(top.pos * 2 <= 200000 && !v[top.pos * 2]){ v[top.pos * 2] = 1; q.push((node){top.pos * 2 , top.step + 1}); } } } int main() { cin >> n >> k; bfs(n); return 0; }
-
0
#include<bits/stdc++.h> using namespace std; int a[100001],que[100001][3]; int main() { int n,k,head,tail,xx,t; cin>>n>>k; if(n==k) { cout<<0<<endl; return 0; } head=0; tail=1; que[1][0]=n; que[1][1]=0; a[n]=1; while(head<tail) { head++; xx=que[head][0]; for(int i=1;i<=3;i++) { if(i==1) t=xx+1; if(i==2) t=xx-1; if(i==3) t=2*xx; if(t>=0 && t<=100000&&a[t]==0) { tail++; que[tail][0]=t; que[tail][1]=que[head][1]+1; a[t]=1; if(t==k) { cout<<que[tail][1]; return 0; } } } } return 0; }
-
-2
#include<bits/stdc++.h> #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 1e6 + 10; const int INF = 0x3f3f3f3f; int m,n; int a[N]; struct node { int x,t; }; int bfs(int x) { queue<node>p; p.push((node){x,0}); a[x]=1; while(!p.empty()) { node t=p.front(); p.pop(); if(t.x+1==m||t.x-1==m||t.x*2==m) return t.t+1; if(t.x+1<N-100&&a[t.x+1]==0) { a[t.x+1]=1; p.push((node){t.x+1,t.t+1}); } if(t.x-1>0&&a[t.x-1]==0) { a[t.x-1]=1; p.push((node){t.x-1,t.t+1}); } if(t.x*2<N-100&&a[t.x<<1]==0) { a[t.x<<1]=1; p.push((node){t.x<<1,t.t+1}); } } } int main() { cin >> n >> m; if(m<=n) cout <<n-m; else cout << bfs(n); return 0; }
- 1
信息
- ID
- 1345
- 时间
- 1500ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 483
- 已通过
- 127
- 上传者