【HDOJ】1104 Remainder

bfs.
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <queue>
 5 #include <iostream>
 6 #include <string>
 7 using namespace std;
 8 
 9 #define MAXN 1005
10 
11 char ops[5] = "+-*%";
12 bool visit[MAXN];
13 int n, m, k;
14 string op;
15 
16 typedef struct node_t {
17     int s, n;
18     string op;
19     node_t (int ss, int nn, string opp) {
20         s = ss;
21         n = nn;
22         op = opp;
23     }
24 } node_t;
25 
26 int bfs() {
27     queue<node_t> Q;
28     int ns[4], tmp;
29     int nn = ((n+1)%k+k)%k;
30     int mk = m*k;
31 
32     Q.push(node_t(0, n, ""));
33     memset(visit, false, sizeof(visit));
34     visit[(n%k+k)%k] = true;
35 
36     while(!Q.empty()) {
37         node_t nd = Q.front();
38         Q.pop();
39         // +
40         ns[0] = (nd.n + m)%mk;
41         // -
42         ns[1] = (nd.n - m)%mk;
43         // *
44         ns[2] = (nd.n * m)%mk;
45         // %
46         ns[3] = (nd.n % m+m)%m%mk;
47         for (int i=0; i<4; ++i) {
48             tmp = (ns[i]%k+k)%k;
49             if (tmp == nn) {
50                 op = nd.op + ops[i];
51                 return nd.s+1;
52             }
53             if (!visit[tmp]) {
54                 visit[tmp] = true;
55                 Q.push(node_t(nd.s+1, ns[i], nd.op+ops[i]));
56             }
57         }
58     }
59 
60     return 0;
61 }
62 
63 int main() {
64     int ans;
65 
66 #ifndef ONLINE_JUDGE
67     freopen("data.in", "r", stdin);
68 #endif
69 
70     while (scanf("%d%d%d", &n, &k, &m)!=EOF && (n||m||k)) {
71         ans =  bfs();
72         printf("%d
", ans);
73         if (ans)
74             cout <<op<<endl;
75     }
76 
77     return 0;
78 }