0x25 广度优先搜索

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

【例题】Bloxorz POJ3322

Bloxorz 是一个风靡世界的小游戏。Bloxorz 的地图是一个 $N$ 行 $M$ 列的矩阵，每个位置可能是硬地（用“.”表示）、易碎地面（用“E”表示）、禁地（用“#”表示）、起点（用“X”表示）或终点（用“O”表示）。你的任务是操作一个 $1*1*2$ 的长方体。这个长方体在地面上有两种放置形式，“立”在地面上（ $1*1$ 的面接触地面）或者“躺”在地面上（ $1*2$ 的面接触地面）。在每一步操作中，可以按上下左右四个键之一。按下按键之后，长方体向对应的方向沿着棱滚动90度。任意时刻，长方体不能有任何部位接触禁地（否则就会掉下去），并且不能立在易碎地面上（否则会因为压强大大掉下去）。字符“X”标识长方体的起始位置，地图上可能有一个“X”或者两个相邻的“X”。地图上唯一的一个字符“O”标识目标位置。求把长方体移动到目标位置（即立在“O”上）所需要的最少步数。如果无解，输出“ Impossible”。在移动过程中，“X”和“O”标识的位置都可以看作是硬地被利用， $3 \leq N, M \leq 500$ 。

这是一道典型的“走地图”类问题，也就是形如“给定一个矩形地图，控制一个物体在地图中按要求移动，求最少步数”的问题。广度优先搜索很擅长解决这种问题——地图的整体形态是固定不变的，只有少数个体或特征随着每一步操作发生改变。我们只需要把这些变化的部分提取为状态，把起始状态加入队列，使用广度优先搜索不断取出队头状态，沿着分支扩展、入队即可。广度优先搜索是逐层遍历搜索树的算法，所有状态按照入队的先后顺序具有层次单调性（也就是步数单调性）。如果每一次扩展恰好对应一步，那么当一个状态第一次被访问（入队）时，就得到了从起始状态到达该状态的最少步数。

在这道题目中，不变的是整个地图，变化的部分有长方体的位置和放置形态。我们可以用一个三元组 $(x,y,lie)$ 代表一个状态（搜索树中的一个节点），其中 $lie = 0$ 表示长方体立在 $(x,y)$ ； $lie = 1$ 表示长方体横向躺着，左半部分位置在 $(x,y)$ ； $lie = 2$ 表示长方体纵向躺着，上半部分在 $(x,y)$ ，并用数组 $d[x][y][lie]$ 记录从起始状态到达

每个状态的最少步数。然后执行广度优先搜索即可。

struct rec { int x, y, lie; }; // 状态
char s[510][510]; // 地图
rec st, ed; // 起始状态和目标状态
int n, m, d[510][510][3]; // 最少步数记录数组
queue<rec> q; // 队列
// 方向数组（方向 0~3 依次代表左右上下）
const int dx[4] = { 0,0,-1,1 }, dy[4] = { -1,1,0,0 };
void parse_st_ed() { // 处理起点和终点
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == '0') {
                ed.x = i, ed.y = j, ed.lie = 0, s[i][j] == '.';
            }
        }
    else if (s[i][j] == 'X') {
        for (int k = 0; k < 3; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (valid(x, y) && s[x][y] == 'X') {
                st.x = min(i, x), st.y = min(j, y);
                st.lie = k<2 ? 1 : 2;
                s[i][j] = s[x][y] == '.';
            }
        }
    } if (s[i][j] == 'X') st.x = i, st.y = j, st.lie = 0;
}

if (next.lie == 1 && s[next.x][next.y + 1] == '#') return 0;  
if (next.lie == 2 && s[next.x + 1][next.y] == '#') return 0;  
return 1;

// next_x[i][j]表示在lie=i时朝方向j滚动后x的变化情况

const int next_x[3][4] = {{0,0,-2,1},{0,0,-1,1},{0,0,-1,2}};

// next_y[i][j]表示在lie=i时朝方向j滚动后y的变化情况

const int next_y[3][4] = {{-2,1,0,0},{-1,2,0,0},{-1,1,0,0}};

// next lie[i][j]表示在 lie=i 时朝方向 j 滚动后 lie 的新值

const int nextlie[3][4] = {{1,1,2,2},{0,0,1,1},{2,2,0,0}};

int bfs(){ //广搜

for (int i = 1; i <= n; i++)  
    for (int j = 1; j <= m; j++)  
        for (int k = 0; k < 3; k++) d[i][j][k] = -1;  
while (q.size()) q.pop();  
d[st.x][st.y][st.lie] = 0;  
q.push(st);  
while (q.size()) {  
    rec now = q.front(); q.pop(); //取出队头  
    for (int i = 0; i < 4; i++) { //向4个方向滚动  
        rec next;  
        next.x = now.x + next_x(now.lie)[i];  
        next.y = now.y + next_y(now.lie)[i];  
        next.lie = next_lie(now.lie)[i];  
        if (!valid(next)) continue;  
        if (d下一篇[x][next.y][next.lie] == -1) { //尚未访问过  
            d下一篇[x][next.y][next.lie] = d下一篇[x][now.y][now.lie] + 1;  
            q.push(next);  
            if (next.x == ed.x && next.y == ed.y && next.lie == ed.lie)  
                return d下一篇[x][next.y][next.lie]; //到达目标  
        }  
    }  
}  
return -1; //无解

}   
int main() { while (cin >> n >> m && n) { for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1); parse_st_ed(); int ans  $=$  bfs(); if (ans  $= = -1$  ) puts("Impossible"); else cout << ans << endl; }

提示：在上述代码中，我们使用next_x, next_y, next Lies等常数数组预先保存了长方体沿4个方向滚动的变化情况，避免了使用大量if语句造成的混乱。这是广搜程序实现中的一个常见技巧。

【例题】矩阵距离BZOJ2252

给定一个 $N$ 行 $M$ 列的01矩阵 $A, A[i][j]$ 与 $A[k][l]$ 之间的曼哈顿距离定义为：

输出一个 $N$ 行 $M$ 列的整数矩阵 $B$ ，其中：

先来思考这样一个问题：给定一个 $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]$ 。如下图所示：

在编写广搜代码中，再次提醒读者注意地图边界的检查、记录数组 $d$ 的初始化，并使用方向常数数组 $dx$ 与 $dy$ 避免多个if分支。参考程序如下：

const int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };  
char s[1020][1020];  
int d[1020][1020], n, m;  
queue<int, int>> q;  
int main() {  
    cin >> n >> m;  
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);  
    memset(d, -1, sizeof(d));  
    for (int i = 1; i <= n; i++)  
        for (int j = 1; j <= m; j++)  
            if (s[i][j] == '1') q.push(make_pair(i,j)), d[i][j] = 0);  
    while (q.size()) {  
        pair<int, int> now = q.front(); q.pop();  
    for (int k = 0; k < 4; k++) {  
        pair<int, int> next(now.first + dx[k], now(second + dy[k]);  
        if (next.first < 1 || next(second < 1 || next.first > n || next(second > m) continue;  
            if (d下一篇[i][next-second] == -1) {  
                d下一篇[i][next-second] = d下一篇[i][now(second] + 1;  
                q.push(next);}  
            }  
    }  
}  
for (int i = 1; i <= n; i++) {  
        for (int j = 1; j <= m; j++) printf("%d ", d[i][j]);  
        puts("");  
}

【例题】Pushing Boxes POJ1475

推箱子游戏相信大家都不陌生，在本题中，你将控制一个人把1个箱子推到目的地。给定一张 $N$ 行 $M$ 列的地图，用字符“.”表示空地，字符“#”表示墙，字符“S”表示人的起始位置，字符“B”表示箱子的起始位置，字符“T”表示箱子的目标位置。求一种移动方案，使箱子移动的次数最少，在此基础上再让人移动的总步数最少。方案中使用大写的“EWSN”（东西南北）表示箱子的推动，使用小写的“ewsn”（东西南北）表示人的移动。 $N,M\leq 20$ 。

样例输入：711

T##. .#

#.##.##

B. #

#.####

...S..#

样例输出：eennwwwwWeeeeeesswwwwwwnNN

在这道题目中，箱子和人都会移动，并且二者的移动可能不是同步的。一个直接的想法是把人和箱子的位置一起组成一个状态，这样的状态是一个四元组，规模是 $O(N^{2}M^{2})$ 。如果直接使用这个算法进行广搜，会出现一些问题：

1. 题目要求先保证箱子移动的总步数 step_box 最少，再保证人移动的总步数 step_man 最少。根据我们之前提到过的广搜的性质，应该让队列中的状态对应的步数二元组（step_box, step_man）保持单调性（即队列中的状态满足第一关键字 step_box 递增，当 step_box 相同时第二关键字 step_man 递增）。
   然而，在对每个状态进行扩展时，有的时候箱子和人移动的步数都会增加，有的时候只有人移动的步数会增加。如果像往常一样简单地把新状态放在队尾，就可能会破坏队列中的状态对应“步数二元组”的单调性。

2. 在队列状态不满足步数单调性时，每个状态只访问一次的广搜会求出错误的答案。我们在下一节 0x26“广搜变形”中会提到几种解决方案，比如使用迭代的思想多次更新一个状态，或者改用优先队列进行广搜。然而这些方案都会进一步增加算法的时间复杂度（至少增加一个log）。本题每个测试点包含很多组数据，上述算法都会导致超时。

进一步分析本问题，我们可以发现，在每次箱子移动后，人一定位于箱子之前处于的位置上。于是，我们可以把每次箱子刚刚移动后，箱子与人的位置打包构成一个状态，

记为 $(x,y,dir)$ ，其中 $(x,y)$ 表示箱子处于第 $x$ 行第 $y$ 列， $dir$ 是一个 $0\sim 3$ 之间的整数值，指示人处于箱子旁边四个位置中的哪一个。如果我们像上一道题目一样使用方向常数数组 $dx$ 和 $dy$ ，那么人的位置就可以表示为 $(x - dx[dir], y - dy[dir])$ 。

另外，我们使用数组 $f_{\text{box}}[x][y][dir]$ 和 $f_{\text{man}}[x][y][dir]$ 分别记录每个状态下箱子和人已经移动的步数。

对于任意一个状态 $(x,y,dir)$ ，都可能有4个分支，代表箱子可能向4个方向移动。我们仍使用方向常数数组，然后枚举方向 $k = 0\sim 3$ ，则扩展到的下一个状态就是 $(x + dx[k], y + dy[k], k)$ ，移动的方式是：

1. 箱子在 $(x, y)$ 处不动，人用尽量少的步数从起点 $(x - dx[dir], y - dy[dir])$ 移动到终点 $(x - dx[k], y - dy[k])$ ，并且途中不能经过 $(x, y)$ 。

2. 人沿着 $k$ 方向推一次箱子，箱子移动到 $(x + dx[k], y + dy[k])$ ，人移动到 $(x, y)$ 。

此后，我们把新状态 $(x + dx[k], y + dy[k], k)$ 入队，并存储新状态对应的 $f_{\text{box}}$ 与 $f_{\text{man}}$ 的值。

这是一个双重BFS算法。从整体上看，算法在对每次箱子移动后的“箱子与旁边的人”这个合体进行BFS。而在这个BFS的每一次状态扩展时，我们再用“对人进行的另一个BFS”求出人在两个位置之间移动的最少步数。

我们在程序设计时常常讲究代码的“模块性”。如果我们把 $(x, y, dir)$ 这个状态扩展时发生的移动写成一个函数 expand，该函数返回箱子和人移动的步数，那么算法本身其实就是一个普普通通的 BFS，只不过它每一步扩展时使用的计算函数 expand 内，恰好又需要使用 BFS 而己。

除了代码编写的“模块性”，读者在理解、设计算法时，也要时刻秉承“模块化”的思想。整个问题有一个大的解决框架，框架的每个细节可能又是一个“小问题”，小问题的解决框架的细节可能还有其他更小的“子问题”，就像一棵树一样逐层深入。读者在设计其中每个问题的算法时，要专注于整体框架，不妨假设细节部分的“小问题”已经处理完毕，争取把每个框架都转化成我们学过的类似“模型”。这样的话，无论多么复杂的问题都会迎刃而解了。

最后，我们还需要讨论上述算法的正确性。对于状态 $(x, y, dir)$ 进行的外层 BFS，在每次状态扩展的移动过程中，箱子一定移动了 1 步，人可能移动了若干步，并且状态中的 $dir$ 相当于移动的方向（还相当于分支来源）。所以，在第二次访问某个状态时，箱子移动的步数一定比第一次多（请读者仔细思考为什么带有 $dir$ 的状态就满足这个性质）。因此，每个状态 $(x, y, dir)$ 只访问一次的这个双重 BFS 算法就可以求出最优解，其状态规模为 $O(NM)$ ，每次扩展最多花 $O(NM)$ 的时间进行内层 BFS，总体时间复杂度不超过 $O(N^2 M^2)$ 。

本题还要求输出一种具体方案，我们可以额外用数组记录最终的每个 $f_{\text{box}}$ 与 $f_{\text{man}}$ 值是从上一步的哪个状态更新而来的（也就是记录搜索树上的父节点），在求出最优解后向前逆推得到箱子的运动轨迹。最后我们按照箱子的运动轨迹，在相邻的两次移动之间重新对人进行 BFS，组合起来即可得到最终的方案。这种记录和逆推的方法是各种搜索、动态规划题目输出方案的常用做法。