2 条题解

  • 1
    @ 2022-08-03 17:37:52

    算法:bfs

    此处bfs为外部循环(同floodfill),dfs会TLE。

    #include <iostream>
    #include <cstring>
    #include <queue>
    #include <cmath>
    using namespace std;
    
    #define in inline
    #define rint register int
    typedef long long LL;
    typedef pair<int,int> PII;
    
    in int read()
    {
        rint x=0,f=0; register char ch=getchar();
        while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
        while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
        return f?-x:x;
    }
    
    /*----------code----------*/
    const int N=1200010;
    int dist[N];
    
    int bfs(int n,int k)
    {
        queue<int> q;
        q.push(n);
        
        memset(dist,-1,sizeof dist);
        dist[n]=0;
        
        while(!q.empty())
        {
            int t=q.front(); q.pop();
            if(t==k) return dist[k];
            
            rint ne[]={t*1.2,t+1,t-1};
            
            for(int i=0;i<3;i++)
                if(ne[i]<N&&dist[ne[i]]==-1)
                {
                    q.push(ne[i]);
                    dist[ne[i]]=dist[t]+1;
                }
        }
    }
    
    int main()
    {
        int n,k; n=read(),k=read();
        
        cout<<bfs(n,k);
        
        return 0;
    }
    
  • 0
    @ 2021-07-21 21:23:43

    bfs模板题。

    #include<bits/stdc++.h>
    using namespace std;
    struct node{
        int now;
        int dis;
    };
    int minv[1200005];
    int main()
    {
        int n,k; cin>>n>>k;
        for(int i=0;i<=1200000;i++) minv[i] = 9999999;
        queue<node> q;
        q.push((node){n,0});
        minv[n] = 0; 
        while(!q.empty())
        {
            node t = q.front();
            int nxt[3] ={t.now*1.2, t.now+1, t.now-1};
            for(int i=0;i<3;i++)
            {
                if(nxt[i]<= 1200000 && minv[nxt[i]] > t.dis+1)
                {
                    minv[nxt[i]] = t.dis+1;
                    q.push((node){nxt[i], t.dis+1}); 
                }
                if(nxt[i] == k)
                {
                    cout<<t.dis+1<<endl;
                    return 0;
                }
            }
            q.pop();
        }
        
        return 0; 
    }
    
    
  • 1

信息

ID
1282
难度
7
分类
(无)
标签
(无)
递交数
41
已通过
9
通过率
22%
被复制
5
上传者