【OI学习笔记】双端队列BFS

双端队列BFS

在基本的BFS广搜中，每次沿着分支的扩展都记一步，我们通过逐层搜索，解决了求起始状态到每个状态的最少步数问题。这其实等价于在一张边权均为1的图上执行BFS，求出每个点相对于起点的最短距离（层次）。每个状态在第一次被访问并入队时，计算出的步数即为所。
但是，如果说图上的边权不全是1呢？就比如当图上的边权是1、0两种状态时，每次拓展都有各自不同的“代价”，那么此时要求出起始状态到每个状态的最小代价就需要用到双端队列来保证队列的两段性和单调性。

deque

deque容器为一个给定类型的元素进行线性处理，像向量一样，它能够快速地随机访问任一个元素，并且能够高效地插入和删除容器的尾部元素。但它又与vector不同，deque支持高效插入和删除容器的头部元素，因此也叫做双端队列。
它就像是vector与queue的结合。
与vector相比，deque在头部增删元素仅仅需要O(1)的时间；
与queue相比，deque像数组一样支持随机访问。
让我们来看看deque的函数基本操作：

1.构造

无参构造：
deque a;　　//<>内自定义数据类型；
带参构造：
deque(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。
deque(n,elem); //构造函数将n个elem拷贝给本身。
deque(const deque &deq); //拷贝构造函数。

2. 头部&尾部的添加和删除(接下来的’dq’为变量名)

dq.push_back(elem); //在容器尾部添加一个数据
dq.push_front(elem); //在容器头部插入一个数据
dq.pop_back(); //删除容器最后一个数据
dq.pop_front(); //删除容器第一个数据

3.中间数据存取

dq.at(idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range。
deque[idx]; //返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
dq.front(); //返回第一个数据。
dq.back(); //返回最后一个数据

4.元素插入

dq.insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。
dq.insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。
dq.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。

5.数据删除

dq.clear(); //移除容器的所有数据
dq.erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。
dq.erase(pos); //删除pos位置的数据，返回下一个数据的位置。

6.迭代指针

dq.begin(); //返回容器中第一个元素的迭代器。
dq.end(); //返回容器中最后一个元素之后的迭代器。
dq.rbegin(); //返回容器中倒数第一个元素的迭代器。
dq.rend(); //返回容器中倒数最后一个元素之后的迭代器。

7.赋值&拷贝

dq.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。
dq.assign(n,elem); //将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符
dq.swap(deq); // 将vec与本身的元素互换

8.大小&判断非空

dq.size(); //返回容器中元素的个数
dq.empty(); //判断容器是否为空
dq.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
dq.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

【例题】电路维修

题解

双端队列主要解决图中边的权值只有0或者1的最短路问题
操作：
每次从队头取出元素，并进行拓展其他元素时
1. 若拓展某一元素的边权是0，则将该元素插入到队头
2. 若拓展某一元素的边权是1，则将该元素插入到队尾
回归到题目：
首先明确的一点是，这里是图中的格子和点是不一样的，点是格子上的角角上的点，每个点都有4个方向可以走，分别对应的是左上角，右上角，右下角，左下角。
特别注意：判断“/”C++中要写成“//”！踩过格子到达想去的点时，需要判断是否需要旋转电线，若旋转电线表示从当前点到想去的点的边权是1，若不旋转电线则边权是0
按左上角，右上角，右下角，左下角遍历的顺序：
1. dx[ ]和dy[ ]表示可以去其他点的方向
2. id[ ]和iy[ ]表示需要踩某个方向的各种才能去到相应的点
3. cs[ ]表示当前点走到4个方向的点理想状态下格子形状(边权是0的状态)
时间复杂度 O(nm)
如下面的程序就用“BFS+双端队列”就解决了该问题：
（蒟蒻的双端队列用STL的deque实现，要程序跑得更快，可以手写双端队列）：

//DC Songxingan
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 510;
int t, n, m, ans[maxn][maxn];
char map[maxn][maxn];
struct Node
{
    int x, y;
};  //坐标
deque<Node> dq;  //双端队列

void BFS()  //广搜
{
    while (!dq.empty())
    {
        Node lin, now;
        lin = dq.front();
        dq.pop_front();
//-----从4个方向搜索可到格点-----
        if (lin.x > 1 && lin.y > 1)  //边界判断
        {
            now.x = lin.x - 1;
            now.y = lin.y - 1;  //更新搜索的点坐标
            int flag = 0;
            if (map[now.x][now.y] != '\\')  //若要旋转则边权为1
            {
                flag = 1;
            }

            if (ans[now.x][now.y] > ans[lin.x][lin.y] + flag)
//判断当前搜索的点是否已经被搜过或是否是最有解
            {
                ans[now.x][now.y] = ans[lin.x][lin.y] + flag;
//边权值为1 放在队尾，为0放在队首
                if (flag)
                    dq.push_back(now);
                else
                    dq.push_front(now);
            }
        }
//接下剩下3个方向搜索同理
        if (lin.x > 1 && lin.y <= m)
        {
            now.x = lin.x - 1;
            now.y = lin.y + 1;
            int flag = 0;
            if (map[now.x][lin.y] != '/')
            {
                flag = 1;
            }

            if (ans[now.x][now.y] > ans[lin.x][lin.y] + flag)
            {
                ans[now.x][now.y] = ans[lin.x][lin.y] + flag;
                if (flag)
                    dq.push_back(now);
                else
                    dq.push_front(now);
            }
        }
        if (lin.x <= n && lin.y <= m)
        {
            now.x = lin.x + 1;
            now.y = lin.y + 1;
            int flag = 0;
            if (map[lin.x][lin.y] != '\\')
            {
                flag = 1;
            }

            if (ans[now.x][now.y] > ans[lin.x][lin.y] + flag)
            {
                ans[now.x][now.y] = ans[lin.x][lin.y] + flag;
                if (flag)
                    dq.push_back(now);
                else
                    dq.push_front(now);
            }
        }
        if (lin.x <= n && lin.y > 1)
        {
            now.x = lin.x + 1;
            now.y = lin.y - 1;
            int flag = 0;
            if (map[lin.x][now.y] != '/')
            {
                flag = 1;
            }

            if (ans[now.x][now.y] > ans[lin.x][lin.y] + flag)
            {
                ans[now.x][now.y] = ans[lin.x][lin.y] + flag;
                if (flag)
                    dq.push_back(now);
                else
                    dq.push_front(now);
            }
        }
    }
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%s", map[i] + 1);
        }
        if ((n + m) % 2 == 1)  //可行性剪枝：如果行数加列数不是偶数则无解
        {
            printf("NO SOLUTION\n");
            continue;
        }
//------初始化------
        Node fir;
        fir.x = 1;
        fir.y = 1;
        dq.clear();
        dq.push_front(fir);
        memset(ans, 0x7f, sizeof(ans));
        ans[1][1] = 0;
        BFS();
        printf("%d\n", ans[n + 1][m + 1]);  //注意输出的是格点
    }
    return 0;
}

【OI学习笔记】双端队列BFS

双端队列BFS

deque

1.构造

2. 头部&尾部的添加和删除(接下来的’dq’为变量名)

3.中间数据存取

4.元素插入

5.数据删除

6.迭代指针

7.赋值&拷贝

8.大小&判断非空

【例题】电路维修

题解

感谢您的支持，我会继续努力的!