4 条题解

  • 3
    @ 2023-1-9 15:22:21
    #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
      @ 2025-3-9 19:52:35
      #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
        @ 2023-11-19 16:40:07
        #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
          @ 2022-7-23 14:27:23
          #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
          上传者