5 条题解

  • 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-7-19 16:52:03
      #include<bits/stdc++.h>
      const int N=2e5+10;
      using namespace std;
      int n,k;
      struct node{
      	int pos,step;
      };
      bool v[N];
      void bfs(){
      	queue<node> q;
      	q.push((node){n,0});
      	v[n]=1;
      	while(!q.empty()){
      		node top=q.front();
      		q.pop();
      		if(top.pos==k){
      			cout<<top.step;
      			exit(0);
      		}
      		if(top.pos+1<=k&&!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<N&&!v[top.pos*2]){
      			v[top.pos*2]=1;
      			q.push((node){top.pos*2,top.step+1});
      		}
      	}
      }
      int main(){
      	cin>>n>>k;
      	bfs();
      }
      
      
      • 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
            标签
            递交数
            593
            已通过
            149
            上传者