hdoj 1226 超级密码【隐式图BFS】

野性酷女 2022-08-13 11:41 26阅读 0赞

题目：[hdoj 1226 超级密码 ][hdoj 1226 _]

分析：这题属于隐式图搜索，状态不是很明显，需要自己建立。

其实搜索说白了就是暴力。

这个题目就是，首先对给出的可以组成的所有的数依次枚举，长度从小到大。

比如第一组样例，因为0不能出现在首位，那么我们枚举首位为1 和 7 看看漫步满足，

满足的话枚举第二位10 11 17 以及 70 71 77 顺便保存他们取余 n 之后的值，这样就可以剪枝，搜索过的就不用重复搜索了。

要求最早出现的BFS即可，第一个搜到的就是。

注意长度不大于500

AC代码：

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <vector>
    #include <cmath>
    #include <queue>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 15;
    int a[20];
    int flag[60000];
    struct Node
    {
        string s;
        int ss;
    };
    Node ans;
    int n,c,m;
    char solve(int x)
    {
        if(x>=0 && x<=9)
            return x+'0';
        return x-10+'A';
    }
    bool BFS()
    {
        memset(flag,0,sizeof(flag));
        queue<Node> q;
        Node now,next;
        for(int i=0;i<m;i++)
        {
            if(a[i]!=0)
            {
                now.s = solve(a[i]);
                now.ss = (a[i]%n);
                if(now.ss == 0)
                {
                    ans = now;
                    return true;
                }
                if(flag[now.ss]==0)
                {
                    flag[now.ss] = 1;
                    q.push(now);
                }
            }
        }
        while(!q.empty())
        {
            now = q.front();
            q.pop();
            //cout<<now.s<<" "<<now.ss<<endl;
            if(now.ss == 0)
            {
                ans = now;
                return true;
            }
            for(int i=0;i<m;i++)
            {
                next.s= now.s+solve(a[i]);
                next.ss = (now.ss*c+a[i])%n;
               // cout<<"NEXT:"<<next.s<<" "<<next.ss<<" "<<a[i]<<endl;
                if(flag[next.ss]==0)
                {
                    flag[next.ss] = 1;
                    q.push(next);
                }
            }
        }
        return false;
    }
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d",&n,&c,&m);
            for(int i=0;i<m;i++)
            {
                char c[10];
                scanf("%s",c);
                if(c[0]>='A' && c[0]<='F')
                    a[i] = (c[0]-'A')+10;
                else
                    a[i] = c[0]-'0';
            }
            sort(a,a+m);
            if(n==0)
            {
                if(a[0]==0)
                    puts("0");
                else
                    puts("give me the bomb please");
                continue;
            }
            if(BFS() && ans.s.size()<=500)
                cout<<ans.s<<endl;
            else
                puts("give me the bomb please");
        }
        return 0;
    }

[hdoj 1226 _]: http://acm.hdu.edu.cn/showproblem.php?pid=1226