STL双向队列下的广搜——好奇怪的游戏

· · 题解

这是一道适合初学搜索的人刷的一道广搜题，然而我写了个神奇的双向队列，估计我是唯一用双向队列写的这道题的人吧。

因为有两匹马，一白一黑，所以我本意是想用单个deque代替两个queue。

然而看了题解，发现好像queue也可以做，看来还是我想多了

具体说这道题之前，我们先来简单了解一下双向队列这个东东（就当是科普了）。

首先，双向队列（deque）是STL中的一个容器

定义的方法如下：

#include<deque>
deque <int>q;

注意，头文件是deque而不是queue（当然也可以像我一样直接bits/stdc++。.h行天下）

接下来是操作;

顾名思义，双向队列是可以进行头尾同时操作的队列，其进出和vector有些相似

q.push_back();//从尾进
q.push_front();//从头进
q.pop_back();//从尾出
q.pop_front();//从头出
q.empty()//是否为空

相比queue，deque还有特殊的功能：

q.clear()//一键清空队列；
cout<<q[1];//随机访问；

deque就像是综合了queue和vector优点的神器！

接下来我们回到这道题，看看deque的特性如何在这体现。 先康康定义

int a[hs][hs];
struct node
{
    int x;
    int y;
    int minns;
};
//结构体封装，更方便！
int sa[13]={0,2,2,-2,-2,-1,-1,1,1,-2,-2,2,2};//用数组预存能走的12个方向，
int sb[13]={0,2,-2,2,-2,-2,2,-2,2,1,-1,1,-1};//省的到时候不停的if—else
int xa,xb,ya,yb;
deque <node>m;今天的主角，双向队列
inline int bfs(int x,int y);

接下来是广搜程序

inline int bfs(int x,int y)
{
    node n;
    n.x=x;//横坐标
    n.y=y;//纵坐标
    n.minns=0;//最短路
    m.push_back(n);//从尾进
    do
    {
        n=m.front();
        m.pop_front();//从头出（注意别从尾出了，这样队列就变成栈了）
        for(fint i=1;i<=12;i++)
        {
        node o;
        o.x=n.x+sa[i];
        o.y=n.y+sb[i];//跳马
        if(o.x==1&&o.y==1&&a[o.x][o.y]==0)
        return o.minns;
        else
        if(o.x>=1&&o.y>=1&&a[o.x][o.y]==0)
        {
        a[o.x][o.y]=1;
        o.minns=n.minns+1;//最短路增加
        m.push_back(o);//接着进队
        }
        }
    }
    while(!m.empty());
}

还是比较基础易懂的。 最后是异常简洁的主程序

signed main()
{
    cin>>xa>>ya>>xb>>yb;
    cout<<bfs(xa,ya)<<endl;第一匹马
    memset(a,0,sizeof(a));//快速清空数组，省去循环嵌套
    m.clear();deque的一键清空特性
    cout<<bfs(xb,yb);第二匹马
    return 0;
}

好了，这样就结束了，如果想更好了解deque，建议做做->P1886

P1886AC代码点我

祝大家AC愉快！