双端队列广搜

介绍

1. 基本作用：求最短距离
2. 基本方法：BFS、双端队列（deque）
3. 适用题目：需要求点到点的最短距离或最短路径，并且边权只有0或1。

代码思路

与基本的BFS很相似，区别主要在于将元素放入队列时，双端队列广搜是将权为0放到队头。权为1放到队尾。

1. 用一个函数寻找最短路径（距离）。
2. 初始化距离（路径）数组。
3. 建立队列存放距离（路径）。
4. 将函数形参放入队列，并改变该坐标的距离（路径）数组。
5. 循环：队列中有元素则一直循环。
6. 遍历周围坐标，遇到不符合的坐标就略过。
7. 不符合的坐标包括：越界、已被访问过（距离（路径）数组已被改变的）、不符合题目条件的。
8. 对于符合条件的坐标，权为0放到队头，权为1放到队尾。

题目应用

175. 电路维修（算法提高课）

175. 电路维修

思路：

不改变电路就能到达的权为0，改变电路才能到的点权为1。

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 510;

int n, m;
char g[N][N];
int dist[N][N];
bool st[N][N];

int bfs()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    deque<PII> q;
    q.push_back({0, 0});
    dist[0][0] = 0;

    char path[5] = "\\/\\/";
    int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};
    int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, 0, -1};

    while(q.size())
    {
        auto t = q.front();
        q.pop_front();

        int x = t.x, y = t.y;
        if(x == n && y == m) return dist[x][y];

        if(st[x][y]) continue;
        st[x][y] = true;

        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || b < 0 || a > n || b > m) continue;

            int ta = x + ix[i], tb = y + iy[i];
            int w = g[ta][tb] != path[i];
            int d = dist[x][y] + w;

            if(d < dist[a][b])
            {
                dist[a][b] = d;
                if(!w) q.push_front({a, b});
                else q.push_back({a, b});
            }
        }

    }
    return -1;
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n >> m;
        for(int i = 0; i < n; i++) cin >> g[i];

        if(n + m & 1) cout << "NO SOLUTION" << endl;
        else
        {
            int res = bfs();
            cout << res << endl;
        }
    }

    return 0;
}

2019. 拖拉机（寒假每日一题2022）

2019. 拖拉机

思路：

到达干草位置权重为1，其他全为0.

代码：

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, first_x, first_y;
int g[N][N];
int dist[N][N];
bool st[N][N];

void bfs()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    deque<PII> q;
    q.push_back({first_x, first_y});
    dist[first_x][first_y] = 0;

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    while(q.size())
    {
        auto t = q.front();
        q.pop_front();

        int x = t.x, y = t.y;

        if(x == 0 && y == 0) return ;

        if(st[x][y]) continue;
        st[x][y] = true;

        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || b < 0 || a >= N || b >= N) continue;

            int w = g[a][b];
            int d = dist[x][y] + w;
            if(d < dist[a][b])
            {
                dist[a][b] = d;
                if(!w) q.push_front({a, b});
                else q.push_back({a, b});
            }

        }

    }
}

int main()
{
    cin >> n >> first_x >> first_y;
    int t1, t2;
    while(n --)
    {
        cin >> t1 >> t2;
        g[t1][t2] = 1;
    }

    bfs();

    cout << dist[0][0] << endl;

    return 0;
}