题解 P1635 【跳跃】

· · 题解

这道题我就直接用BFS暴力了，最后竟然过了，神奇。

主要思路就是BFS每次扩展，用map判重，直到可以了或走的次数超过了就跳出循环

但是每次都要去模那个数，不然太大了。。。

#include<cstdio>
#include<map>
#include<iostream>
using namespace std;
map<long long ,int>ma;
long long f[5000001][2];
long long head=0,tail=1;
inline void bfs(long long z)//BFS
{
    head++;
    f[head][0]=z;
    f[head][1]=0;//先把他在的坐标加入队列
    ma[z]=1;
    if(z%1000000007==0)
    {
        cout<<0<<endl;
        return;
    }
    do
    {
        long long x=f[head][0];
        int o=(x*4+3)%1000000007;//每次他有两种扩展方式，乘4加3或乘8加7
        if(!ma.count(o))//如果不在队列，就加入队列
        {
        ++tail;
        f[tail][0]=o;//f[a][0]表示数，f[a][1]表示步数
        ma[o]=1;
        f[tail][1]=f[head][1]+1;//这个步数就是当前加一
        if(f[tail][1]>100000)//如果超过了限制，就输出-1
        {
            cout<<-1<<endl;
            return;
        }
        if((o)%1000000007==0)//如果符合条件
        {
            cout<<f[tail][1]<<endl;
            return ;
        }
        }
        int u=(x*8+7)%1000000007;
        if(!ma.count(u))//同上
        {
        ++tail;
        f[tail][0]=u;
        ma[u]=1;
        f[tail][1]=f[head][1]+1;
        if(f[tail][1]>100000)
        {
            cout<<-1<<endl;
            return;
        }
        if((u)%1000000007==0)
        {
            cout<<f[tail][1]<<endl;
            return ;
        }
        }
        head++;
    }while(head<=tail);
}
int main()
{
    long long x;
    cin>>x;
    bfs(x);
    return 0;
}
我好像是跑的最慢的（显然我太弱了，想不到下面两个大佬的做法）