[USACO07OPEN]Catch That Cow
题目:洛谷P1588、HDU2717
题目大意:有一个人在点$n$,一头牛在点$k$,人每秒能从$x$移动到点$x+1$、$x-1$、$2x$,牛不会动,求最少多少秒后人能移动到牛所在的$k$。
思路:BFS。按照题意进行广搜。
注意:题目数据较大,如中途计算中的点$x$大于100000或小于1,则不放入队列中。
两处题目读入不太一样。
细节见代码。
C++ Code:
1 #include<cstdio>
2 #include<queue>
3 #include<cstring>
4 using namespace std;
5 bool b[100051];
6 int main(){
7 int n,k;
8 while(scanf("%d%d",&n,&k)!=EOF){
9 if(n>=k){//特判n≥k的情况
10 printf("%d\n",n-k);continue;
11 }
12 queue<int>q1,q2;
13 q1.push(n);
14 q2.push(0);
15 memset(b,1,sizeof(b));
16 b[n]=0;
17 while(!q1.empty()){
18 int p=q1.front();q1.pop();
19 int P=q2.front();q2.pop();
20 int l=p-1;
21 if(l&&b[l]){
22 if(l==k){
23 printf("%d\n",P+1);break;
24 }
25 b[l]=0;
26 q1.push(l);
27 q2.push(P+1);
28 }
29 l=p+1;
30 if(l<=100000&&b[l]){
31 if(l==k){
32 printf("%d\n",P+1);break;
33 }
34 b[l]=0;
35 q1.push(l);
36 q2.push(P+1);
37 }
38 l=p*2;
39 if(l<=100000&&b[l]){
40 if(l==k){
41 printf("%d\n",P+1);break;
42 }
43 b[l]=0;
44 q1.push(l);
45 q2.push(P+1);
46 }
47 }
48 }
49 return 0;
50 }
转载于//www.cnblogs.com/Mrsrz/p/6921104.html
还没有评论,来说两句吧...