ural 1495 bfs

定义状态visit[i][j]表示最后一位是i且该数字mod n的余数是j的情况，然后按位来bfs即可，转移时先考虑1再考虑2，这样求出来的答案就是长度和数值都最小的了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 1000007;
 7 int n, head, tail;
 8 bool visit[3][N];
 9 
10 struct Node
11 {
12     int d, r, len, pre;
13     Node(){}
14     Node( int _d, int _r, int _len, int _pre )
15     {
16         d = _d, r = _r, len = _len, pre = _pre;
17     }
18 } q[N << 1];
19 
20 void dfs( int x )
21 {
22     if ( x == -1 ) return ;
23     dfs( q[x].pre );
24     printf("%d", q[x].d);
25 }
26 
27 void bfs()
28 {
29     memset( visit, 0, sizeof(visit) );
30     head = tail = 0;
31     q[tail++] = Node( 1, 1 % n, 1, -1 );
32     q[tail++] = Node( 2, 2 % n, 1, -1 );
33     visit[1][1 % n] = 1;
34     visit[2][2 % n] = 1;
35     while ( head < tail )
36     {
37         if ( q[head].len > 30 )
38         {
39             break;
40         }
41         if ( q[head].r == 0 )
42         {
43             dfs(head);
44             putchar('
');
45             return ;
46         }
47         for ( int k = 1; k <= 2; k++ )
48         {
49             int rr = ( q[head].r * 10 + k ) % n;
50             if ( !visit[k][rr] )
51             {
52                 q[tail++] = Node( k, rr, q[head].len + 1, head );
53                 visit[k][rr] = 1;
54             }
55         }
56         head++;
57     }
58     printf("Impossible
");
59 }
60 
61 int main ()
62 {
63     while ( scanf("%d", &n) != EOF )
64     {
65         bfs();
66     }
67     return 0;
68 }