hdu 1226(bfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1226

思路：广搜，每一个状态用一个结构体来保存，记录数组的长度，然后根据长度来扩展就可以了，这里值得注意的地方余数判重以及求大数取模。

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 #define MAXN 555
 8 #define MAXM 5555
 9 struct Node{
10     int num[MAXN];
11     int len;
12 };
13 bool digit[22];
14 bool mark[MAXM];
15 int N,C,M;
16 
17 //判断C进制的密码转10进制能否被N整除
18 int Judge(Node &p){
19     int len=p.len,tmp=0;
20     for(int i=1;i<=len;i++){
21         tmp=(tmp*C+p.num[i])%N;
22     }
23     return tmp;
24 }
25 
26 
27 bool bfs(){
28     memset(mark,false,sizeof(mark));
29     queue<Node>Q;
30     Node p,q;
31     p.len=1;
32     Q.push(p);
33     while(!Q.empty()){
34         p=Q.front();
35         Q.pop();
36         for(int i=(p.len==1?1:0);i<16;i++){
37             if(digit[i]){
38                 q=p;
39                 q.num[q.len]=i;
40                 int mod=Judge(q);
41                 if(mod){
42                     if(!mark[mod]&&q.len+1<=500){
43                         mark[mod]=true;
44                         q.len+=1;
45                         Q.push(q);
46                     }
47                 }else {
48                     for(int i=1;i<=q.len;i++){
49                         printf("%X",q.num[i]);
50                     }
51                     puts("");
52                     return true;
53                 }
54             }
55         }
56     }
57     return false;
58 }
59 
60 
61 int main(){
62     int _case,x;
63     scanf("%d",&_case);
64     while(_case--){
65         scanf("%d%d%d",&N,&C,&M);
66         memset(digit,false,sizeof(digit));
67         for(int i=1;i<=M;i++){
68             scanf("%x",&x);
69             digit[x]=true;
70         }
71         if(N==0){
72             if(digit[0])puts("0");
73             else puts("give me the bomb please");
74         }else if(!bfs()){
75             puts("give me the bomb please");
76         }
77     }
78     return 0;
79 }