普通广度优先搜索

迷宫问题

给定一个 \(n\times m\) 的迷宫，标为 # 的地方是不能走的墙，标为 . 的地方时是可以走的空地。现在你要从 \((1,1)\) 走到 \((n,m)\)，请问最少需要走多少步？（保证有解）

我们可以先考虑深搜：设 \(f(x,y,s)\) 表示当前在格子 \((x,y)\)，已经走了 \(s\) 步，那么接下来就有四个方向可以选择——上左下右。我们可以选择任意一个方向来转移，然后进行递归搜索。如果我们已经搜到了解，不那么我们就与之前的解取最小值，因为题目中已经告诉了我们是最小步数。注意我们需要判断是否已经走出了边界，也就是添加可行性剪枝。

代码

const int kD[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};  // 四个方向

void dfs(int x, int y, int s) {
  if (x < 1 || x > n || y < 1 || y > n || a[x][y] == '#') {
    return;
  }
  if (x == n && y == m) {
    ans = min(ans, s);
    return;
  }
  for (auto i : kD) {
    dfs(x + i[0], y + i[1], s + 1);
  }
}

然后我们发现，如果当前 \(s\) 已经超过或等于了之前的 \(ans\) 值，那么就不必要继续搜索了。毕竟步数又不能 \(-1\)，是不是？

代码

if (s >= ans) {
  return;
}

虽然这种搜索方法已经看起来很优了，但是我们考虑一种最坏情况——万一我们的深搜最开始就选择了一个错误的方向，然后在错误的地方一直搜了半天都搜不到答案，那么该怎么办？因此，我们在解决这种迷宫问题的时候，不能单单向一个方向搜，而是一层层地一起搜，那么这个问题就解决了。

这就是广度优先搜索。我们每次搜索的都是一层层地状态，也就是 \(s\) 一样的状态。这样子到了任意一个格子，最开始经过的肯定是最优的，因此每一个格子就只用经过一次了。时间复杂度就可以降到 \(\mathcal O(nm)\)。

至于如何实现，我们就可以使用一个队列，因为队列是先进先出的，而先进来的状态正好就是旧的不要的状态。因此我们只需要将不要的状态从队头弹出，新来的状态从队尾进入就行了。

代码

void record(int x, int y, int s) {  // 记录一个新状态
  if (x < 1 || x > n || y < 1 || y > m || f[x][y]) {  // 不要的状态去掉
    return;
  }
  q.emplace(x, y, s);  // 进入队列
  f[x][y] = 1;  // 标记为已到达
}

void bfs(int x, int y) {
  for (q.emplace(x, y, 0); q.size(); q.pop()) {  // 加入初始状态并不断循环，每一个状态转移完就不用了
    if (q.front().x == n && q.front().y == m) {  // 记录答案
      ans = q.front().s;
      return;
    }
    for (auto i : kD) {  // 枚举四个方向
      record(q.front().x + i[0], q.front().y + i[1], q.front().s + 1);
    }
  }
}

注意

广度优先搜索跟队列本身是没有什么关系的，只是队列的先进先出机制正好可以满足普通的广度优先搜索，但是并不是所有的广度优先搜索都需要队列。

评论