洛谷题解 P1747 【好奇怪的游戏】

  • A+
所属分类:代码笔记 信息技术

这是一道bfs模版题,思路是分别从两个马的位置一直到搜到(1,1)为止,在过程中累加步数,根据广搜层层拓展的原理可知最先搜到(1,1)时一定是最优解

思路和大佬们差不多对吧,其实我主要想说说C++STL队列的应用,懒人必备,具体见代码注释

  1. #include<iostream>
  2. #include<queue> //使用STL队列的头文件
  3. #include<cstring>
  4. using namespace std;
  5. int x1,y1,x2,y2;
  6. struct node{
  7.     int x,y;
  8.     int s;
  9. };
  10. //棋盘上一个点定为一个整体,x y为坐标,s为到这点所需最短步数
  11. int dx[12]={2,2,-2,-2,-1,-1,1,1,-2,-2,2,2};
  12. int dy[12]={2,-2,2,-2,-2,2,-2,2,1,-1,1,-1};
  13. //枚举田字、日字的12种走法
  14. bool b[1000][1000]; //记录点是否走过,防止重复拓展
  15. queue<node> q; //定义一个队列,类型为node,queue是关键字,< >里填变量类型,也可以是int、float等等,q是队列名
  16. int bfs(int x,int y) //广搜函数,x y为起点坐标
  17. {
  18.     node a;
  19.     a.x=x,a.y=y,a.s=0;
  20.     q.push(a);
  21.     //先初始化,把起点步数设为0,放入队列,用STL是不是很方便简洁
  22.     do{
  23.         a=q.front(); //引用队首元素,注意并不删除
  24.         q.pop(); //队首元素出队
  25.         for(int i=0;i<12;i++) //枚举12种走法
  26.         {
  27.             node c; //c记录下一步走到的点
  28.             c.x=a.x+dx[i],c.y=a.y+dy[i];
  29.             if(c.x>=1 && c.y>=1 && b[c.x][c.y]==false)
  30.             {
  31.                 if(c.x==1 && c.y==1){
  32.                     return c.s; //到(1,1)就直接返回结果
  33.                 }
  34.                 b[c.x][c.y]=true//记录此点已走过
  35.                 c.s=a.s+1; //这一点的最短步数=上一层(也就是拓展出它的那个点,点a)的最短步数+1步
  36.                 q.push(c); //把新拓展的c点放入队列
  37.             }
  38.         }
  39.     }while(!q.empty()); //当队列不为空时继续
  40. }
  41. int main()
  42. {
  43.     cin>>x1>>y1>>x2>>y2;
  44.     cout<<bfs(x1,y1)<<endl; //第一匹马
  45.     memset(b,0,sizeof(b));
  46.     while(!q.empty()) q.pop();
  47.     //千万记得b这个标记数组要清零,而且搜到(1,1)时队列可能还没空,要清空
  48.     cout<<bfs(x2,y2); //第二匹马
  49.     return 0;
  50. }

总结下STL队列的用法:

  1. queue<int> a; //定义一个int类型的队列a
  2. a.front(); //返回队列a的队首元素,并不删除
  3. a.pop(); //删除队首元素(出队)
  4. a.push(x); //将x入队
  5. a.empty(); //检查a是否为空,空则返回true
xcc

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: