POJ3278

快来打我* 2021-11-29 09:56 114阅读 0赞

之前用数组存的每一个位置的步数情况，开的数组大小是100010，过了，后来想改成结构体写，结构体只用再定义一个标记数组，我标记数组也开的100010，然后就RE了，开成200000就过了

完整代码

#include <iostream>
    #include <cstring>
    #include <queue>
    using namespace std;
    int k,vis[200000]; 
    int u[3]={
        1,2,3};
    
    struct node
    {
        int p,s;
        node(int a,int b)
        {
            p=a;
            s=b;    
        }    
    };
    
    void bfs(int n)
    {
        queue<node> q;
        q.push(node(n,0));
        while(!q.empty())
        {
            node t=q.front();
            q.pop();
            if(t.p==k)
            {
                cout<<t.s<<endl;
                return ;
            }
            for(int i=0;i<3;i++)
            {
                int tx=t.p;
                if(u[i]==1)//左移 
                {
                    if(!vis[tx-1] && tx-1>=0 && tx-1<=100000)
                    {
                        vis[tx-1]=1;
                        q.push(node(tx-1,t.s+1));
                    }
                }
                else if(u[i]==2)//右移 
                {
                    if(!vis[tx+1] && tx+1>=0 && tx+1<=100000)
                    {
                        vis[tx+1]=1;
                        q.push(node(tx+1,t.s+1));
                    }
                }
                else if(u[i]==3)//乘2 
                {
                    if(!vis[tx*2] && tx*2>=0 && tx*2<=100000)
                    {
                        vis[tx*2]=1;
                        q.push(node(tx*2,t.s+1));
                    }
                }    
            }    
        }    
    }
    
    int main()
    {
        int n;
        cin>>n>>k;
        vis[n]=1;
        bfs(n);
        return 0;
    }

转载于:https://www.cnblogs.com/benzikun/p/11210612.html