双端队列BFS

在一般的广度优先搜索中，每次沿分支扩展“一步”，逐层搜索，已求解起始状态到每个状态的最小步数

这等价于在一个边权为 1 的图中执行广度优先遍历，求出每个点相对于起点的最短距离

广度优先遍历使用的辅助队列满足：“队列中的状态的层数满足两端性和单调性”

因此每个状态在第一次被访问并入队时，所计算出的步数即为所求

如果边权不是全 1，那该如何处理呢？ 接下来引入其他两种广搜变形的方法，解决该问题

首先是边权为 0 或 1 的情况，就会用到 双端队列

每次扩展一步时，遇到边权为 0，则将该状态更新，并加入队首；遇到边权为 1，则将该状态更新，并加入队尾

该方法仍保持了队列的两端性和单调性，读者自证不难

优先队列BFS

对于更加具有普遍性的情况，即每次扩展都有不同的“代价”时，求出初始状态每个状态的最小代价，就相当于在一个带权图上求从起点到每个节点的最短路

此时可以使用 优先队列BFS，即 Dijkstra 算法，时间复杂度为 O(Nlog⁡N)O(N \log N)

简单总结

  • 问题只计最小部署，等价于在边权都为 1 的图上求最短路
    • 使用普通的 BFS，时间复杂度 O(N)O(N)
  • 问题每次扩展的代价可能是 0 或 1，等价于在边权只有 0 和 1 的图上求最短路
    • 使用双端队列BFS，时间复杂度 O(N)O(N)
  • 问题每次扩展的代价是任意数值，等价于一般的最短路问题
    • 使用优先队列BFS，时间复杂度 O(Nlog⁡N)O(N \log N)

双向BFS

同0x24节中介绍的双向搜索思想

在已知目标状态，以及目标状态往回变换的手段时，可以使用双向BFS

起始状态和目标状态两边轮流进行，每次各扩展一层

当两边各自有一个状态在记录数组中重复时，说明两个搜索相遇了，可以合并得出起点到终点的最小步数

习题

电路维修

题目描述

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。

有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个 RR 行 CC 列的网格（R,C≤500R,C≤500），如下图所示。

每个格点都是电线的接点，每个格子都包含一个电子元件。

电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。

在旋转之后，它就可以连接另一条对角线的两个接点。

电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。

她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。

不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。

注意：只能走斜向的线段，水平和竖直线段不能走。

输入格式

输入文件包含多组测试数据。

第一行包含一个整数 TT，表示测试数据的数目。

对于每组测试数据，第一行包含正整数 RR 和 CC，表示电路板的行数和列数。

之后 RR 行，每行 CC 个字符，字符是 / 和 \ 中的一个，表示标准件的方向。

输出格式

对于每组测试数据，在单独的一行输出一个正整数，表示所需的最小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出 NO SOLUTION。

数据范围

1≤R,C≤500,1≤T≤51≤R,C≤500, 1≤T≤5

输入样例：

1
2
3
4
5
1
3 5
\\/\\
\\///
/\\\\

输出样例：

1
1

样例解释

样例的输入对应于题目描述中的情况。

只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。

解析

对该网格图进行建图，对于两个对角线上的点 xx 和 yy 来说

若网格线和对角线重合，则连接一条边权为 0 的边，否则连接一条边权为 1 的边

然后对该图求一个最短路即可，由于边权为 0 或 1，因此采用双端队列即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 510;

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

void solve()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[0][0] = 0;
    deque<PII> deq;
    deq.push_back({0, 0});

    char state[] = {"\\/\\/"};
    int dx[] = {1, 1, -1, -1}, dy[] = {1, -1, -1, 1};
    int ix[] = {0, 0, -1, -1}, iy[] = {0, -1, -1, 0};
    
    while (deq.size())
    {
        PII t = deq.front();
        deq.pop_front();
        if (st[t.x][t.y]) continue;
        if (t.x == n && t.y == m) break;
        st[t.x][t.y] = true;

        for (int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a > n || b < 0 || b > m) continue;
            int w = g[t.x + ix[i]][t.y + iy[i]] != state[i];
            int d = w + dist[t.x][t.y];
            
            if (d < dist[a][b])
            {
                dist[a][b] = d;
                if (w) deq.push_back({a, b});
                else deq.push_front({a, b});
            }
        }
    }
    cout << dist[n][m] << endl;
}
int main()
{
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;
        for (int i = 0; i < n; i ++ ) cin >> g[i];
        if ((n + m) & 1) puts("NO SOLUTION");
        else solve();
    }
    return 0;
}

装满的油箱

题目描述

有 NN 个城市（编号 0、1…N−10、1…N−1）和 MM 条道路，构成一张无向图。

在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。

现在你需要回答不超过 100 个问题，在每个问题中，请计算出一架油箱容量为 CC 的车子，从起点城市 SS 开到终点城市 EE 至少要花多少油钱？

注意： 假定车子初始时油箱是空的。

输入格式

第一行包含两个整数 NN 和 MM。

第二行包含 NN 个整数，代表 NN 个城市的单位油价，第 ii 个数即为第 ii 个城市的油价 pip_i。

接下来 MM 行，每行包括三个整数 u,v,du,v,d，表示城市 uu 与城市 vv 之间存在道路，且车子从 uu 到 vv 需要消耗的油量为 dd。

接下来一行包含一个整数 qq，代表问题数量。

接下来 qq 行，每行包含三个整数 C、S、EC、S、E，分别表示车子油箱容量 CC、起点城市 SS、终点城市 EE。

输出格式

对于每个问题，输出一个整数，表示所需的最少油钱。

如果无法从起点城市开到终点城市，则输出 impossible。

每个结果占一行。

数据范围

1≤N≤1000,1≤M≤10000,1≤pi≤100,1≤d≤100,1≤C≤1001≤N≤1000, 1≤M≤10000, 1≤p_i≤100, 1≤d≤100, 1≤C≤100

输入样例：

1
2
3
4
5
6
7
8
9
10
5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

输出样例：

1
2
170
impossible

解答

直接拆点，以二元组 {city, fuel} 作为一个点，进行建图，然后做一遍最短路即可

每一次扩展有两种选择：

  1. 当前油箱未满，且加一升油后 {city, fuel} + price[city] < {city, fuel + 1} 那么就在当前城市加一升油，并扩展出去
  2. 当前油量可以抵达下一个城市且 cost < {next, fuel - dist} 那就扩展出去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int INF = 0x3f3f3f3f;

int n, m, q;
int C, S, E;
int h[1010], e[20010], w[20010], ne[20010], idx;
int p[1010];
int dist[1010][110];
bool st[1010][110];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    dist[S][0] = 0;
    heap.push({0, {S, 0}});
    while (heap.size())
    {
        auto t = heap.top(); heap.pop();
        int cost = t.x, ver = t.y.x, fuel = t.y.y;
        
        if (st[ver][fuel]) continue;
        st[ver][fuel] = true;
        if (ver == E) return cost;
        
        if (fuel < C && dist[ver][fuel + 1] > cost + p[ver])
        {
            dist[ver][fuel + 1] = cost + p[ver];
            heap.push({cost + p[ver], {ver, fuel + 1}});
        }
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i], d = w[i];
            if (fuel >= d && dist[j][fuel - d] > cost)
            {
                dist[j][fuel - d] = cost;
                heap.push({cost, {j, fuel - d}});
            }
        }
    }
    return -1;
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> p[i];
    for (int i = 0; i < m; i ++ )
    {
        int u, v, d;
        cin >> u >> v >> d;
        add(u, v, d), add(v, u, d);
    }
    cin >> q;
    while (q -- )
    {
        cin >> C >> S >> E;
        int t = dijkstra();
        if (~t) cout << t << endl;
        else puts("impossible");
    }
    return 0;
}

噩梦

题目描述

给定一张 N×MN×M 的地图，地图中有 11 个男孩，11 个女孩和 22 个鬼。

字符 . 表示道路，字符 X 表示墙，字符 M 表示男孩的位置，字符 G 表示女孩的位置，字符 Z 表示鬼的位置。

男孩每秒可以移动 33 个单位距离，女孩每秒可以移动 11 个单位距离，男孩和女孩只能朝上下左右四个方向移动。

每个鬼占据的区域每秒可以向四周扩张 22 个单位距离，并且无视墙的阻挡，也就是在第 kk 秒后所有与鬼的曼哈顿距离不超过 2k2k 的位置都会被鬼占领。

注意： 每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。

求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。

输入格式

第一行包含整数 TT，表示共有 TT 组测试用例。

每组测试用例第一行包含两个整数 NN 和 MM，表示地图的尺寸。

接下来 NN 行每行 MM 个字符，用来描绘整张地图的状况。（注意：地图中一定有且仅有 11 个男孩，11 个女孩和 22 个鬼）

输出格式

每个测试用例输出一个整数 SS，表示最短会合时间。

如果无法会合则输出 −1−1。

每个结果占一行。

数据范围

1<n,m<8001<n,m<800

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X

输出样例：

1
2
3
1
1
-1

解答

双向BFS即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 810;

int n, m;
char g[N][N];
int st[N][N];
PII boy, girl, ghost[2];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool check(int a, int b, int t)
{
    if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] == 'X') return false;
    for (int i = 0; i < 2; i ++ )
        if (abs(ghost[i].x - a) + abs(ghost[i].y - b) <= 2 * t)
            return false;
    return true;
}
int solve()
{
    memset(st, 0, sizeof st);
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i];
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'M') boy = {i, j};
            else if (g[i][j] == 'G') girl = {i, j};
            else if (g[i][j] == 'Z') ghost[cnt ++ ] = {i, j};
    
    queue<PII> qb, qg;
    qb.push(boy);
    qg.push(girl);

    int step = 0;
    while (qb.size() || qg.size())
    {
        step ++ ;
        for (int i = 0; i < 3; i ++ )
        {
            for (int j = 0, siz = qb.size(); j < siz; j ++ )
            {
                PII t = qb.front(); qb.pop();
                int x = t.x, y = t.y;
                if (!check(x, y, step)) continue;
                for (int k = 0; k < 4; k ++ )
                {
                    int a = x + dx[k], b = y + dy[k];
                    if (check(a, b, step))
                    {
                        if (st[a][b] == 2) return step;
                        if (!st[a][b])
                        {
                            st[a][b] = 1;
                            qb.push({a, b});
                        }
                    }
                }
            }
        }
        for (int i = 0; i < 1; i ++ )
        {
            for (int j = 0, siz = qg.size(); j < siz; j ++ )
            {
                PII t = qg.front(); qg.pop();
                int x = t.x, y = t.y;
                if (!check(x, y, step)) continue;
                for (int k = 0; k < 4; k ++ )
                {
                    int a = x + dx[k], b = y + dy[k];
                    if (check(a, b, step))
                    {
                        if (st[a][b] == 1) return step;
                        if (!st[a][b])
                        {
                            st[a][b] = 2;
                            qg.push({a, b});
                        }
                    }
                }
            }
        }
    }
    return -1;
}
int main()
{
    int T;
    cin >> T;
    while (T -- ) cout << solve() << endl;
    return 0;
}