問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1426思路:
典型的BFS，每次擴(kuò)展都在末尾加上0或者1，例如從1開始，1->10、1->11，10->100，10->101...
根據(jù)這點(diǎn)，就可以寫出AC的代碼，不過這樣所需內(nèi)存會(huì)比較高昂，因?yàn)楸４娴拿總€(gè)狀態(tài)都是long long，并且狀態(tài)數(shù)目非常多
參考網(wǎng)上代碼，發(fā)現(xiàn)這里可以應(yīng)用鴿巢原理
對(duì)于m取模，其結(jié)果只有0, 1, ..., m-1這幾種可能，因此很可能出現(xiàn)重復(fù)
另外，如果擴(kuò)展前remainder是k, 那么擴(kuò)展之后的remainder可以通過((k*10)+0/1)%num計(jì)算得到
如何記錄結(jié)果也是比較tricky的，這里在每個(gè)狀態(tài)中只保留一位以及指向擴(kuò)展前狀態(tài)的指針，輸出的時(shí)候只要遞歸即可
代碼:
1 struct EACH {
2 int remainder;
3 int digit;
4 struct EACH *pre;
5 }queue[QUEUE_MAX];
6 int hash[REMAINDER_MAX];
7 int head, tail;
8 int num;
9
10 void
11 output(struct EACH *end)
12 {
13 if(end==NULL)
14 return;
15 output(end->pre);
16 printf("%d", end->digit);
17 }
18
19 void
20 bfs()
21 {
22 int cur_rem, next_rem;
23 queue[tail].remainder = 1%num;
24 queue[tail].digit = 1;
25 queue[tail].pre = NULL;
26 hash[queue[tail].remainder] = 1;
27 while(head <= tail) {
28 ++head;
29 cur_rem = queue[head].remainder;
30 if(cur_rem == 0) {
31 output(queue+head);
32 printf("\n");
33 return;
34 }
35 next_rem = (cur_rem*10+0)%num;
36 if(!hash[next_rem]) {
37 ++tail;
38 queue[tail].remainder = next_rem;
39 queue[tail].digit = 0;
40 queue[tail].pre = queue+head;
41 hash[next_rem] = 1;
42 }
43 next_rem = (cur_rem*10+1)%num;
44 if(!hash[next_rem]) {
45 ++tail;
46 queue[tail].remainder = next_rem;
47 queue[tail].digit = 1;
48 queue[tail].pre = queue+head;
49 hash[next_rem] = 1;
50 }
51 }
52 }