3 条题解

  • 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;
    }
    
    • 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
        时间
        1000ms
        内存
        256MiB
        难度
        6
        标签
        递交数
        287
        已通过
        89
        上传者