[USACO07OPEN]Catch That Cow

川长思鸟来 2021-09-29 14:50 298阅读 0赞

题目:洛谷P1588、HDU2717

题目大意:有一个人在点$n$,一头牛在点$k$,人每秒能从$x$移动到点$x+1$、$x-1$、$2x$,牛不会动,求最少多少秒后人能移动到牛所在的$k$。

思路:BFS。按照题意进行广搜。

注意:题目数据较大,如中途计算中的点$x$大于100000或小于1,则不放入队列中。

两处题目读入不太一样。

细节见代码。

C++ Code:

  1. 1 #include<cstdio>
  2. 2 #include<queue>
  3. 3 #include<cstring>
  4. 4 using namespace std;
  5. 5 bool b[100051];
  6. 6 int main(){
  7. 7 int n,k;
  8. 8 while(scanf("%d%d",&n,&k)!=EOF){
  9. 9 if(n>=k){//特判n≥k的情况
  10. 10 printf("%d\n",n-k);continue;
  11. 11 }
  12. 12 queue<int>q1,q2;
  13. 13 q1.push(n);
  14. 14 q2.push(0);
  15. 15 memset(b,1,sizeof(b));
  16. 16 b[n]=0;
  17. 17 while(!q1.empty()){
  18. 18 int p=q1.front();q1.pop();
  19. 19 int P=q2.front();q2.pop();
  20. 20 int l=p-1;
  21. 21 if(l&&b[l]){
  22. 22 if(l==k){
  23. 23 printf("%d\n",P+1);break;
  24. 24 }
  25. 25 b[l]=0;
  26. 26 q1.push(l);
  27. 27 q2.push(P+1);
  28. 28 }
  29. 29 l=p+1;
  30. 30 if(l<=100000&&b[l]){
  31. 31 if(l==k){
  32. 32 printf("%d\n",P+1);break;
  33. 33 }
  34. 34 b[l]=0;
  35. 35 q1.push(l);
  36. 36 q2.push(P+1);
  37. 37 }
  38. 38 l=p*2;
  39. 39 if(l<=100000&&b[l]){
  40. 40 if(l==k){
  41. 41 printf("%d\n",P+1);break;
  42. 42 }
  43. 43 b[l]=0;
  44. 44 q1.push(l);
  45. 45 q2.push(P+1);
  46. 46 }
  47. 47 }
  48. 48 }
  49. 49 return 0;
  50. 50 }

转载于:https://www.cnblogs.com/Mrsrz/p/6921104.html

发表评论

表情:
评论列表 (有 0 条评论,298人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Catch That Cow

    think: 1广度优先搜索(队列思想) 2以结构数组为基础的队列思想 3反思:自己因为vis数组有的初始化位置不对,导致runtime error.??? hi

    相关 USACO10HOL】 Cow Politics

    题目大意 给出k组点,求出组内两点间的最大距离 核心思路 考虑贪心,每组内的最深一点一定是两最远距离点对之一。 证明很简单,可以分为在该点的祖先相同和祖先不同的