問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3278思路:
簡(jiǎn)單的BFS，一次AC
使用一個(gè)數(shù)組visited[MAX_NUM]來(lái)判重
代碼:
1 #define ADD(temp, cur) ++tail; \
2 queue[tail].num = temp; \
3 queue[tail].moves = cur+1; \
4 visited[temp] = 1;
5
6 int
7 bfs()
8 {
9 int cur_num, cur_moves, temp;
10 queue[tail].num = n;
11 queue[tail].moves = 0;
12 visited[queue[tail].num] = 1;
13 while(head <= tail) {
14 ++head;
15 cur_num = queue[head].num;
16 cur_moves = queue[head].moves;
17 if(cur_num == k)
18 return cur_moves;
19 temp = cur_num - 1;
20 if(temp>=0 && temp<MAX_NUM && !visited[temp]) {
21 ADD(temp, cur_moves);
22 }
23 temp = cur_num + 1;
24 if(temp>=0 && temp<MAX_NUM && !visited[temp]) {
25 ADD(temp, cur_moves);
26 }
27 temp = cur_num<<1;
28 if(temp>=0 && temp<MAX_NUM && !visited[temp]) {
29 ADD(temp, cur_moves);
30 }
31 }
32 }