hdu 4474 bfs

和上一题大同小异，经过思考，visit数组可以省去第一维。
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 10007;
 7 const int M = 10;
 8 int n, m, head, tail;
 9 bool visit[N];
10 bool digit[M];
11 
12 struct Node
13 {
14     int d, r, pre;
15     Node(){}
16     Node( int _d, int _r, int _pre )
17     {
18         d = _d, r = _r, pre = _pre;
19     }
20 } q[N];
21 
22 void dfs( int x )
23 {
24     if ( x == -1 ) return ;
25     dfs( q[x].pre );
26     printf("%d", q[x].d);
27 }
28 
29 void bfs()
30 {
31     memset( visit, 0, sizeof(visit) );
32     head = tail = 0;
33     for ( int i = 1; i < M; i++ )
34     {
35         if ( !digit[i] && !visit[i % n] )
36         {
37             q[tail++] = Node( i, i % n, -1 );
38             visit[i % n] = 1;
39         }
40     }
41     while ( head < tail )
42     {
43         if ( q[head].r == 0 )
44         {
45             dfs(head);
46             putchar('
');
47             return ;
48         }
49         for ( int k = 0; k < M; k++ )
50         {
51             if ( digit[k] ) continue;
52             int rr = ( q[head].r * 10 + k ) % n;
53             if ( !visit[rr] )
54             {
55                 q[tail++] = Node( k, rr, head );
56                 visit[rr] = 1;
57             }
58         }
59         head++;
60     }
61     printf("-1
");
62 }
63 
64 int main ()
65 {
66     int _case = 1;
67     while ( scanf("%d%d", &n, &m) != EOF )
68     {
69         memset( digit, 0, sizeof(digit) );
70         while ( m-- )
71         {
72             int tmp;
73             scanf("%d", &tmp);
74             digit[tmp] = 1;
75         }
76         printf("Case %d: ", _case++);
77         bfs();
78     }
79     return 0;
80 }