HDU 1226 超级密码

中文题我就不说什么了 最近写的一道 数位bfs （个人取名……若有误还请提出更正）
结果马上就用上了 只不过题意更加明显而已 （之前还以为是很高级的想法 没想到只是在高级搜索的 Level 1 推荐出现 心酸……
其实还是和之前写的代码差不多拉 我自己消化了一下

坑点：1 注意判断 n == 0的时候 2.密码长度超过500 就不用继续了

AC Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn=5005;
const int inf=0x3f3f3f3f;
int n,m,k,num[20],ans;
char ch[3];
bool vis[maxn];

struct node
{
    char ch;
    int pre,mod,step;
}que[maxn*10];

void print(int x)
{
    if(que[x].pre!=-1)
        print(que[x].pre);
    putchar(que[x].ch);
}

void bfs()
{
    int l=1,r=1;
    for(int i=0;i<k;i++) if(num[i])
    {
        que[r].pre=-1;
        que[r].step=1;
        vis[que[r].mod=num[i]%n]=true;
        if(num[i]<10)
            que[r].ch=num[i]+'0';
        else que[r].ch=num[i]-10+'A';
        if(que[r].mod==0)
        {
            ans=r;
            return ;
        }
        r++;
    }
    while(l<r)
    {
        int step=que[l].step;//如果在这里判断step  时间从15MS  变成31MS   就是这么玄学
        for(int i=0;i<k;i++)
        {
            int tmp=que[r].mod=(que[l].mod*m+num[i])%n;
            if(!vis[tmp])
            {
                vis[tmp]=true;
                que[r].pre=l;
                que[r].step=step+1;
                if(num[i]<10)
                    que[r].ch=num[i]+'0';
                else que[r].ch=num[i]-10+'A';
                if(tmp==0&&step+1<=500)
                {
                    ans=r;
                    return ;
                }
                r++;
            }
        }
        l++;
    }
}

int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d %d %d",&n,&m,&k);
        for(int i=0;i<k;i++)
        {
            scanf("%s",ch);
            if(ch[0]<='9'&&ch[0]>='0')
                num[i]=ch[0]-'0';
            else num[i]=ch[0]-'A'+10;
        }
        sort(num,num+k);
        if(n==0)
        {
            if(num[0]==0) puts("0");
            else puts("give me the bomb please");
            continue;
        }
        memset(vis,false,sizeof vis);
        ans=-1;
        bfs();
        if(ans==-1) puts("give me the bomb please");
        else
        {
            print(ans);
            puts("");
        }
    }
    return 0;
}