http://acm.hdu.edu.cn/showproblem.php?pid=1226

难以想到怎么去bfs,还是对状态的划分不明确,知道了之后感觉还是挺简单的。

这题关键是密码可能很长,然后判断是否整除用到了一点技巧,确保不会溢出,输出的时候是用递归回溯输出。

因为同一个数可以取多次,而最终取的是数值最小的,故输入之后从小到大排序,然后从第一个数到最后一个数每次添加一遍,直到找到合适的为止.

为了便于输出用了数组模拟队列.

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 struct point 7 { 8     int mod; 9     int digit;10     int pre;11     int step;12 }Queue[5001],init={
   0,0,-1};13 int n,c,m;14 int num[20];15 int used[5010];16 17 void echo(int x)18 {19     if(Queue[x].pre==-1) return;20     else echo(Queue[x].pre);21     if(Queue[x].digit>=0&&Queue[x].digit<=9) printf("%c",Queue[x].digit+'0');22     else printf("%c",Queue[x].digit+'A'-10);23 }24 void bfs()25 {26     memset(used,0,sizeof(used));27     int front=0,rear=1;28     bool flag=0;29     Queue[0]=init;30     while(front!=rear)31     {32         point e=Queue[front];33         for(int i=0;i
         
          =500) continue;38             used[ans]=1;39             Queue[rear].pre=front;40             Queue[rear].digit=num[i];41             Queue[rear].mod=ans;42             Queue[rear].step=e.step+1;43             if(ans==0) {echo(rear);printf("\n");flag=1;break;}44             rear++;45         }46         front++;47     }48     if(!flag) printf("give me the bomb please\n");49 }50 int main()51 {52     freopen("a.txt","r",stdin);53     int t;54     char str[20];55     scanf("%d",&t);56     while(t--)57     {58         scanf("%d%d%d",&n,&c,&m);59         getchar();60         for(int i=0;i
          
           ='0'&&str[0]<='9') num[i]=str[0]-'0';64 else num[i]=10+str[0]-'A';65 // printf("%d\n",num[i]);66 }67 sort(num,num+m);68 if(n==0)69 {70 if(num[0]==0) printf("0\n");71 else printf("give me the bomb please\n");72 }73 else bfs();74 }75 return 0;76 }