双端队列

简介

普通的 BFS 每一步的代价都是相同的，而双端队列是专门用来处理代价可以为 1 和 0 两种的这种特殊情况：遇到无代价的直接插队到队首，有代价的插到队尾

当然，你也可以使用优先队列，甚至是各种图遍历算法，但是我感觉解决这种问题还是使用双端队列比较简单

例题

最经典的还是 Acwing175 电路维修

点击查看题目

  • 题目描述

    达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。翰翰的家里有一辆飞行车。有一天飞行车的电路板突然出现了故障，导致无法启动。电路板的整体结构是一个 RR 行 CC 列的网格，如下图所示。

    电路.png

    每个格点都是电线的接点，每个格子都包含一个电子元件。电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。在旋转之后，它就可以连接另一条对角线的两个接点。电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。

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

  • 输入格式

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

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

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

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

  • 输出格式

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

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

  • 数据范围

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

  • 输入样例：

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

  • 输出样例：

    1
    1

这道题就非常经典，如果邻接点之间有线连接的话，通过代价就是 0 ，没有的话通过代价就是 1

所以就只需要改变入队时的策略就行了，就像上面说的那样，0 代价的直接插队到队首

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 512;

// 四方向：右下，左下，右上，左上
// 向下为 x 正，向右为 y 正
const int dx[4] = {1, 1, -1, -1};
const int dy[4] = {1, -1, 1, -1};

// 先定义格子坐标：指格子左上角的点的坐标
// 下面的数组是需要判断的格子与当前点的坐标差
// 例如你要往右下走，就需要判断本点(x+0,y+0)的格子，而向右上走，就需要判断正上方点(x+0,y-1)的格子
const int bolckDx[4] = {0, 0, -1, -1};
const int bolckDy[4] = {0, -1, 0, -1};
const char freeBlock[4] = {'\\', '/', '/', '\\'};
int dist[M][M], n, r, c;
char Map[M][M];

struct node
{
    int x, y;
    node(int x, int y) : x(x), y(y) {}
    node() {}
};

deque<node> q;

void init()
{
    memset(dist, -1, sizeof(dist));
    // memset(Map, 0, sizeof(Map));
    q.clear();
}

inline bool check(int x, int y)
{
    return !(x < 0 || x > r || y < 0 || y > c);
}

void bfs()
{

    q.push_back(node(0, 0));
    dist[0][0] = 0;
    while (!q.empty())
    {
        node now = q.front();
        q.pop_front();

        for (int i = 0; i < 4; i++)
        {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            int bx = now.x + bolckDx[i];
            int by = now.y + bolckDy[i];
            if (nx < 0 || nx > r || ny < 0 || ny > c)
                continue;

            if (Map[bx][by] != freeBlock[i] && (dist[nx][ny] > dist[now.x][now.y] + 1 || dist[nx][ny] == -1))
            {
                dist[nx][ny] = dist[now.x][now.y] + 1;
                q.push_back(node(nx, ny));
            }
            else if (Map[bx][by] == freeBlock[i] && (dist[nx][ny] > dist[now.x][now.y] || dist[nx][ny] == -1))
            {
                dist[nx][ny] = dist[now.x][now.y];
                q.push_front(node(nx, ny));
            }
        }
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    while (n--)
    {
        init();
        scanf("%d%d", &r, &c);
        for (int i = 0; i < r; i++)
        {
            scanf("%s", Map[i]);
        }
        if ((r + c) % 2)
        {
            printf("NO SOLUTION\n");
            continue;
        }
        bfs();

        printf("%d\n", dist[r][c]);
    }
}

而另外也有一道比较经典的，就是我上学期栽过的，杭电2022Debug杯的T9

Hash 判重

在搜索的时候，保存历史状态并进行判重是很重要的，不然就会多走回头路

这就牵扯到 Hash（哈希，或称散列）函数

按照我的理解，简单地说，哈希就是把一个大数据（例如几GB的磁盘文件，又例如广搜中的某个搜索状态）转换压缩成一条特征值（字符串或是数字）

这个特征值有个特点，就是原数据哪怕改变一点点，这个特征值都会改变，比如说：很大的数字对一个质数取模得到特征值

当然你可以问如果有两组数据哈希过后的值是一样的怎么办？这就是哈希碰撞，如果要考虑碰撞的话，就牵扯到开散列和闭散列了，这个暂时不谈

image-20220912201733413

哈希可以举一个生活中的例子，比如 SHA256 和 SHA512 值，在下载文件的时候经常会给出，考虑到长度，SHA512 几乎没有哈希碰撞的可能

这个值是通过计算文件的内容得到的，即便是发生了最微小的改变，哈希值也会大不相同

在下载后，可以在本地重新计算哈希值，然后进行对比，检查下载时是否出错

扯远了，简单地说，就是要根据需要决定是否要构造哈希函数，来更方便地保存搜索中的中间状态，例如八数码里面的康拓展开一样

常见的哈希函数有：

  1. 状态压缩

    一般基础的状压就是将一行的状态压成一个数，这个数的二进制形式反映了这一行的情况，例如一组物品选或不选，用 1 代表选选，0 代表不选

  2. 直接取余

    选取一个大质数 M 作为除数

  3. 平方取中

    计算关键值的平方，然后取中间的 K 位

  4. 折叠法

    把字符串中所有字符的 ASCII 码加起来，可以考虑取余

双向广搜

简介

双向广搜很好理解，朴素 BFS 是从当前状态开始搜索，直到搜到目标状态

而双向广搜就是从起点和终点同时向对方搜索，若在中间发生相遇，这条拼接的路径就是最优解

通常有两种策略

  1. 两个方向交替搜索
  2. 每次都选择结点个数较少的那个方向先扩展（更优）

例题

经典题目：Knight Moves(Poj1915)

点击查看题目

  • Background
    Mr Somurolov, fabulous chess-gamer indeed, asserts that no one else but him can move knights from one position to another so fast. Can you beat him?

  • The Problem
    Your task is to write a program to calculate the minimum number of moves needed for a knight to reach one point from another, so that you have the chance to be faster than Somurolov.
    For people not familiar with chess, the possible knight moves are shown in Figure 1.

    img

  • Input
    The input begins with the number n of scenarios on a single line by itself.
    Next follow n scenarios. Each scenario consists of three lines containing integer numbers. The first line specifies the length l of a side of the chess board (4<=l<=3004 <= l <= 300). The entire board has size l∗ll * l. The second and third line contain pair of integers {0, …, l-1}*{0, …, l-1} specifying the starting and ending position of the knight on the board. The integers are separated by a single blank. You can assume that the positions are valid positions on the chess board of that scenario.

  • Output
    For each scenario of the input you have to calculate the minimal amount of knight moves which are necessary to move from the starting point to the ending point. If starting point and ending point are equal,distance is zero. The distance must be written on a single line.

  • Sample Input

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    3
    8
    0 0
    7 0
    100
    0 0
    30 50
    10
    1 1
    1 1

  • Sample Output

    1
    2
    3
    5
    28
    0

其实就是找两点最短路径，但是棋盘只能走日字

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
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 512;
const int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
const int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dis[2][N][N];
bool vis[2][N][N];
int m, n, sx, sy, tx, ty, ans;
struct point
{
    int x, y;
    point(int x = 0, int y = 0) : x(x), y(y) {}
};
queue<point> q[2];

void init()
{
    ans = 0;
    memset(vis, 0, sizeof(vis));
    memset(dis, 0, sizeof(dis));
    while (!q[0].empty())
        q[0].pop();
    while (!q[1].empty())
        q[1].pop();
}

bool expand(int k)
{
    int x = q[k].front().x, y = q[k].front().y, d = dis[k][x][y];
    q[k].pop();
    for (int i = 0; i < 8; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[k][nx][ny])
        {
            dis[k][nx][ny] = d + 1;
            vis[k][nx][ny] = 1;
            q[k].push(point(nx, ny));
            if (vis[1 - k][nx][ny])
            {
                ans = dis[k][nx][ny] + dis[1 - k][nx][ny];
                return true;
            }
        }
    }
    return false;
}

void bfs()
{
    q[0].push(point(sx, sy));
    q[1].push(point(tx, ty));
    vis[0][sx][sy] = vis[1][tx][ty] = 1;
    while (!q[0].empty() && !q[1].empty())
    {
        // printDis();
        if (q[0].size() < q[1].size())
        {
            if (expand(0))
                return;
        }
        else
        {
            if (expand(1))
                return;
        }
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    scanf("%d", &m);
    while (m--)
    {
        init();
        scanf("%d", &n);
        scanf("%d %d", &sx, &sy);
        scanf("%d %d", &tx, &ty);

        if (sx != tx || sy != ty)
            bfs();

        printf("%d\n", ans);
    }
}