算法竞赛进阶指南 搜索 0x25 广度优先搜索

在0x21节中，我们介绍了图的广度优先遍历，在0x22节中，我们又定义了深度优先搜索过程产生的“搜索树”结构。如果我们把问题状态空间类比成一张图，那么广度优先搜索就相当于对这张图的广度优先遍历。类似地，我们依然借助一个队列来实现广度优先搜索，起初，队列中仅包含起始状态。在广度优先搜索的过程中，我们不断从队头取出状态，对于该状态面临的所有分支，把沿着每条分支到达的下一个状态（如果尚未访问过或者能够被更新成更优的解）插入队尾。重复执行上述过程直到队列为空。

1、AcWing 172. 立体推箱子

题意 ：

• 每个用例输出一个整数表示所需的最少步数，如果无解则输出 Impossible。
• 3≤N,M≤500

思路 ：

• 这是一道典型的“走地图“类问题，也就是形如”给定一个矩形地图，控制一个物体在地图中按要求移动，求最少步数”的问题。广度优先搜索很擅长解决这种问题——地图的整体形态是固定不变的，只有少数个体或特征随着每一步操作发生改变。我们只需要把这些变化的部分提取为状态，把起始状态加入队列，使用广度优先搜索不断取出队头状态，沿着分支扩展、入队即可。广度优先搜索是逐层遍历搜索树的算法，所有状态按照入队的先后顺序具有层次单调性（也就是步数单调性）。如果每一次扩展恰好对应一步，那么当一个状态第一次被访问（入队）时，后得到了从起始状态到达该状态的最少步数。
• 在这道题目中，不变的是整个地图，变化的部分有长方体的位置和放置形态。我们可以用一个三元组(x, y, lie)代表一个状态（搜索树中的一个节点），其中lie = 0表示长方体立在(x, y)；lie = 1表示长方体横向躺着，左半部分位置在(x, y)；lie = 2表示长方体纵向躺着，上半部分在(x, y)，并用数组d[x][y][lie]记录从起始状态到达每个状态的最少步数，然后执行广度优先搜索即可。为了程序实现方便，我们用数字0～3分别代指左、右、上、下四个方向。

#include 
#include 
#include 
using namespace std;
const int N = 510;

struct State {
    int x, y, lie;
};

int n, m;
char g[N][N];
int dist[N][N][3];

bool check(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return false;
    return g[x][y] != '#';
}
int bfs(State start, State end) {
    queue<State> que;
    que.push(start);
    dist[start.x][start.y][start.lie] = 0;
    
    int d[3][4][3] = {
        {{0, -2, 1}, {0, 1, 1}, {-2, 0, 2}, {1, 0, 2}},
        {{0, -1, 0}, {0, 2, 0}, {-1, 0, 1}, {1, 0, 1}},
        {{0, -1, 2}, {0, 1, 2}, {-1, 0, 0}, {2, 0, 0}}
    };
    
    while (que.size()) {
        auto t = que.front(); que.pop();
        for (int i = 0; i < 4; ++ i) {
            State next = {t.x + d[t.lie][i][0], t.y + d[t.lie][i][1], d[t.lie][i][2]};
            int x = next.x, y = next.y, lie = next.lie;
            if (!check(x, y)) continue;
            if (lie == 0) {
                if (g[x][y] == 'E') continue;
            } else if (lie == 1) {
                if (!check(x, y + 1)) continue;
            } else {
                if (!check(x + 1, y)) continue;
            }
            if (dist[x][y][lie] == -1) {
                dist[x][y][lie] = dist[t.x][t.y][t.lie] + 1;
                que.push(next);
            }
        }
    }
    return dist[end.x][end.y][end.lie];
}

int main() {
    while (scanf("%d%d", &n, &m), n || m) {
        for (int i = 0; i < n; ++ i) scanf("%s", g[i]);
        memset(dist, -1, sizeof dist);
        
        State start = {-1}, end;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                if (g[i][j] == 'X' && start.x == -1) {
                    if (g[i + 1][j] == 'X') start = {i, j, 2};
                    else if (g[i][j + 1] == 'X') start = {i, j, 1};
                    else start = {i, j, 0};
                }
                else if (g[i][j] == 'O') end = {i, j, 0};
            }
        }
        int ans = bfs(start, end);
        if (ans == -1) cout << "Impossible" << endl;
        else cout << ans << endl;
    }
}

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

2、AcWing 173. 矩阵距离

题意 ：

• 1≤N,M≤1000

思路 ：

• 先来思考这样一个问题，给定一个N * M的01矩阵和一个起点（0表示可通行点，1表示禁止点），每一步可以向上、下、左、右四个方向之一移动1个单位距离，求从起点出发能够到达哪些位置，以及到达每个位置的最少步数。这是广度优先搜索的最基本应用，读者应该都不陌生，我们也称BFS求解该问题的算法为 flood-fill，就好像在起点倒水，看能覆盖多大的一片区域。
• 本题可以看作一道有多个起始状态的flood-fill问题。我们把矩阵A中每一个1都看作起点，整个矩阵的所有位置都可以通行，对于每个位置，在从任何一个起点出发都可以的情况下，求到达该位置所需要的最少步数（也就是距离该位置最近的起点的距离）。
• 在这种具有多个等价的起始状态的问题中，我们只需要在BFS开始之前把这些起始状态全部插入队列。根据BFS逐层搜索的性质，BFS的过程就相当于每个起点先扩展1层，再扩展2层，3层，依此类推。所以当每个位置(x, y)第一次被访问时，就相当于距离它最近的那个起点扩展到了它，此时从那个起点到(x, y)经历的步数就是最短距离B[x][y]

#include 
#include 
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10;

int n, m;
char g[N][N];
int dist[N][N];
PII q[N * N];

void bfs() {
    memset(dist, -1, sizeof dist);
    
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    
    int hh = 0, tt = -1;
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            if (g[i][j] == '1') {
                q[ ++ tt] = {i, j};
                dist[i][j] = 0;
            }
        }
    }
    while (hh <= tt) {
        PII t = q[hh ++ ];
        for (int i = 0; i < 4; ++ i) {
            int x = t.first + dx[i], y = t.second + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (dist[x][y] != -1) continue;
            dist[x][y] = dist[t.first][t.second] + 1;
            q[ ++ tt] = {x, y};
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++ i) scanf("%s", g[i]);
    bfs();
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            printf("%d ", dist[i][j]);
        }
        puts("");
    }
}

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

（Skip）3、AcWing 174. 推箱子