6 条题解

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