1 从两端搜索
广度优先搜索(BFS):从迷宫到最少步数 从起点逐层扩展,第一次发现终点时得到最少步数。若每个状态平均产生
当终点已知,而且能够枚举一个状态的前驱时,可以从起点、终点分别搜索,在中间连接两条路径。
下面的有向图中,从
正向先发现
在分支较均衡、重复状态较少的搜索树中,两侧各搜索约
2 反向搜索
设两侧距离为:
:从起点 到 的最少步数。 :从 到终点 的最少步数。
反向 BFS 要沿反图扩展。原图有边
两侧都发现状态
3 按层相遇
每次选择当前待扩展节点较少的一侧,扩展完整的一层。这一层产生的所有相遇候选取最小值,随后结束搜索。选择较小的一层只影响效率,不改变最优性。
证明如下。假设扩展前,两侧已经分别发现距离不超过
若存在长度不超过
现在正向完整扩展一层,新相遇点给出的路径长度至多为
这个结论依赖三个条件:单位边权、正确的反向转移、按整层扩展。不要把代码改成每次只取一个节点、重新选择方向后立即返回第一次相遇。
4 代码实现
输入 n m s t,随后输入 -1。
expand 开始时记录队尾,保证这一轮只处理原有的一层,新加入的节点留到下一轮。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 5;
vector<int> g[2][maxn]; // 0:原图;1:反图
int dis[2][maxn], q[2][maxn];
int head[2], tail[2];
// 队列中尚未处理的节点恰好是一层;只扩展这一层。
int expand(int side) {
int end = tail[side], answer = INT_MAX;
while (head[side] < end) {
int u = q[side][head[side]++];
for (int v : g[side][u]) {
if (dis[side][v] != -1) continue;
dis[side][v] = dis[side][u] + 1;
q[side][tail[side]++] = v;
if (dis[side ^ 1][v] != -1) {
answer = min(answer, dis[side][v] + dis[side ^ 1][v]);
}
}
}
return answer;
}
int bfs(int s, int t) {
memset(dis, -1, sizeof(dis));
head[0] = head[1] = tail[0] = tail[1] = 0;
dis[0][s] = dis[1][t] = 0;
q[0][tail[0]++] = s;
q[1][tail[1]++] = t;
if (s == t) return 0;
while (head[0] < tail[0] && head[1] < tail[1]) {
// 选择较小的整层,不能只取一个节点就重新选择方向。
int side = (tail[0] - head[0] <= tail[1] - head[1]) ? 0 : 1;
int answer = expand(side);
if (answer != INT_MAX) return answer;
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, s, t;
cin >> n >> m >> s >> t;
while (m--) {
int u, v;
cin >> u >> v;
g[0][u].push_back(v);
g[1][v].push_back(u); // 原图 u -> v,反图 v -> u
}
cout << bfs(s, t) << '\n';
return 0;
}
在显式图上,每个方向至多访问每个节点、每条边一次,时间和空间复杂度均为
5 字串变换
题目:luogu P1032: [NOIP 2002 提高组] 字串变换(疑似错题)。
给定起始串
把整个字符串看作一个节点,一次替换看作一条有向边。反向搜索时,必须把每条规则的左右两端交换:
| 正向规则 | 反向规则 |
|---|---|
ab → x |
x → ab |
x → yz |
yz → x |
例如正向路径是 cab → cx → cyz,反向就从 cyz 经 cx 回到 cab。从目标串继续使用原规则,得到的不是前驱状态。
5.1 状态生成
对每条规则,枚举左串在当前串中的所有出现位置,每次只替换一处。出现位置可以重叠:规则 aa → b 作用于 aaa,能够产生 ba 和 ab。
字符串状态用哈希表记录最短距离,入队时判重。输入串长度不超过
5.2 搜索边界
初始时两侧半径之和为
若
完整代码
#include <bits/stdc++.h>
using namespace std;
pair<string, string> rule[2][10];
int rule_count;
queue<string> q[2];
unordered_map<string, int> dis[2]; // 字符串状态无法直接用整数数组下标
int expand(int side) {
int count = q[side].size(), answer = INT_MAX;
while (count--) { // 新入队的下一层留到下一轮处理
string s = q[side].front();
q[side].pop();
int step = dis[side].at(s);
for (int i = 0; i < rule_count; ++i) {
const auto &[from, to] = rule[side][i];
// 从 pos + 1 继续查找,保留重叠的出现位置。
for (size_t pos = s.find(from); pos != string::npos;
pos = s.find(from, pos + 1)) {
string next = s.substr(0, pos) + to + s.substr(pos + from.size());
if (!dis[side].emplace(next, step + 1).second) continue;
q[side].push(next);
auto it = dis[side ^ 1].find(next);
if (it != dis[side ^ 1].end()) {
answer = min(answer, step + 1 + it->second);
}
}
}
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string start, goal, from, to;
cin >> start >> goal;
while (cin >> from >> to) {
rule[0][rule_count] = {from, to};
rule[1][rule_count++] = {to, from}; // 反向搜索必须交换规则两端
}
if (start == goal) {
cout << 0 << '\n';
return 0;
}
q[0].push(start);
q[1].push(goal);
dis[0][start] = dis[1][goal] = 0;
// 每轮只让一侧的搜索半径增加 1;总半径最多增加到 10。
for (int round = 0; round < 10 && !q[0].empty() && !q[1].empty(); ++round) {
int side = (q[0].size() <= q[1].size()) ? 0 : 1;
int answer = expand(side);
if (answer != INT_MAX) {
cout << answer << '\n';
return 0;
}
}
cout << "NO ANSWER!\n";
return 0;
}
设两侧共发现
完整题解:pcs2:字串变换。
6 相关题解
暂无相关题解