這道題目是利用廣度優(yōu)先搜索的算法我
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 typedef struct node{
5 int x,step;
6 }Node;
7 struct queue{
8 Node array[100001];
9 int front,rear;
10 }Queue;
11 int N,K;
12 int visit[100001];
13 void enqueue(Node data);
14 Node dequeue();
15 int judge();
16 int bfs();
17 int main()
18 {
19 while(scanf("%d %d",&N,&K) != EOF){
20 Queue.front = Queue.rear = 0;
21 memset(visit,0,sizeof(visit));
22 if(N == K)printf("0\n");
23 else
24 printf("%d\n",bfs());
25 }
26 system("pause");
27 return 0;
28 }
29
30 void enqueue(Node data)
31 {
32 Queue.array[Queue.rear].x = data.x;
33 Queue.array[Queue.rear].step = data.step;
34 Queue.rear++;
35 }
36 Node dequeue()
37 {
38 Node data;
39 data.x = Queue.array[Queue.front].x;
40 data.step = Queue.array[Queue.front].step;
41 Queue.front++;
42 return data;
43 }
44 int judge()
45 {
46 if(Queue.front == Queue.rear)return 0;
47 return 1;
48 }
49
50 int bfs()
51 {
52 Node lc,lx;
53 lx.x = N;
54 lx.step = 0;
55 visit[N] = 1;
56 enqueue(lx);
57 while(judge()){
58 lc = dequeue();
59 for(int i = 0;i < 3;i++){
60 if(i == 0){
61 lx.x = lc.x-1;
62 lx.step = lc.step+1;
63 if(lx.x == K)return lx.step;
64 else if(!visit[lx.x] && lx.x >= 0 && lx.x < 100001){
65 visit[lx.x] = 1;
66 enqueue(lx);
67 }
68 }
69 if(i == 1){
70 lx.x = lc.x+1;
71 lx.step = lc.step+1;
72 if(lx.x == K)return lx.step;
73 else if(!visit[lx.x] && lx.x >= 0 && lx.x < 100001){
74 visit[lx.x] = 1;
75 enqueue(lx);
76 }
77 }
78 if(i == 2){
79 lx.x = lc.x*2;
80 lx.step = lc.step+1;
81 if(lx.x == K)return lx.step;
82 else if(!visit[lx.x] && lx.x >= 0 && lx.x < 100001){
83 visit[lx.x] = 1;
84 enqueue(lx);
85 }
86 }
87 }
88 }
89 }
90
用的是C，隊(duì)列得自己寫，如果是C++的話，可以直接調(diào)用Queue庫(kù)，減少很多代碼。