广搜变形 | 搜索

参考《算法竞赛进阶指南》、AcWing题库

双端队列BFS

在最基本的广度优先搜索中, 每次沿着分支的扩展都记为 “一步”, 我们通过逐层搜索, 解决了求从起始状态到每个状态的最少步数的问题。这其实等价于在一张边权均为 1 的图上执行广度优先遍历, 求出每个点相对于起点的最短距离 (层次)。在树与图的遍历中我们曾讨论过这个问题, 并得到了 “队列中的状态的层数满足两段性和单调性” 的结论。从而我们可以知道, 每个状态在第一次被访问并入队时, 计算出的步数即为所求。

然而, 如果图上的边权不全是 1 呢? 换句话说, 如果每次扩展都有各自不同的 “代价", 我们想求出起始状态到每个状态的最小代价, 应该怎么办呢? 我们不妨先来讨论图上的边权要么是 1、要么是 0 的情况。

---

175. 电路维修

题目描述

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。

有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个 $R$ 行 $C$ 列的网格（$R,C≤500$），如下图所示。

每个格点都是电线的接点，每个格子都包含一个电子元件。

电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。

在旋转之后，它就可以连接另一条对角线的两个接点。

电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。

她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。

不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。

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

输入格式

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

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

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

之后 $R$ 行，每行 $C$ 个字符，字符是"/"和"\"中的一个，表示标准件的方向。

输出格式

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

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

数据范围

$1 \le R,C \le 500$,
$1 \le T \le 5$

输入样例：

1
3 5
\\/\\
\\///
/\\\\ 

输出样例：

1 

样例解释

样例的输入对应于题目描述中的情况。

只需要按照下面的方式旋转标准件，就可以使得电源和发动机之间连通。

算法分析

我们可以把电路板上的每个格点 (横线与坚线的交叉点) 看作无向图中的节点。若两个节点 $x$ 和 $y$ 是某个小方格的两个对角, 则在 $x$ 与 $y$ 之间连边。若该方格中的标准件 (对角线) 与 $x$ 到 $y$ 的线段重合, 则边权为 0 ; 若垂直相交, 则边权为 1 (说明需要旋转 1 次才能连上)。然后, 我们在这个无向图中求出左上角到右下角的最短距离, 就得到了答案。

这是一张边权要么是 0 、要么是 1 的无向图。在这样的图上, 我们可以通过双端队列广搜来计算。算法的整体框架与一般的广搜类似, 只是在每个节点上沿分支扩展时稍作改变。如果这条分支是边权为 0 的边, 就把沿该分支到达的新节点从队头入队; 如果这条分支是边权为 1 的边, 就像一般的广搜一样从队尾入队。这样一来, 我们就仍然能保证, 任意时刻广搜队列中的节点对应的距离值都具有 “两段性” 和 “单调性”, 每个节点虽然可能被更新 (入队) 多次, 但是它第一次被扩展 (出队) 时, 就能得到从左上角到该节点的最短距离, 之后再被取出可以直接忽略, 时间复杂度为 $O(R * C)$ 。

#include <deque>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 506;
int r, c, d[N][N];
bool v[N][N];
char s[N][N];
vector<pair<pair<int, int>, int> > p[N][N];
deque<pair<int, int> > q;

void add(int x1, int y1, int x2, int y2, int z) {
	p[x1][y1].push_back(make_pair(make_pair(x2, y2), z));
}

void dlwx() {
	cin >> r >> c;
	for (int i = 1; i <= r; i++) cin >> (s[i] + 1);
	if ((r & 1) != (c & 1)) cout << "NO SOLUTION" << endl;
	for (int i = 0; i <= r; i++)
		for (int j = 0; j <= c; j++)
			p[i][j].clear();
	for (int i = 1; i <= r; i++)
		for (int j = 1; j <= c; j++)
			if (s[i][j] == '/') {
				add(i - 1, j - 1, i, j, 1);
				add(i, j, i - 1, j - 1, 1);
				add(i, j - 1, i - 1, j, 0);
				add(i - 1, j, i, j - 1, 0);
			} else {
				add(i - 1, j - 1, i, j, 0);
				add(i, j, i - 1, j - 1, 0);
				add(i, j - 1, i - 1, j, 1);
				add(i - 1, j, i, j - 1, 1);
			}
	memset(d, 0x3f, sizeof(d));
	d[0][0] = 0;
	memset(v, 0, sizeof(v));
	q.clear();
	q.push_back(make_pair(0, 0));
	while (q.size()) {
		int x = q.front().first, y = q.front().second;
		q.pop_front();
		v[x][y] = 1;
		if (x == r && y == c) {
			cout << d[r][c] << endl;
			return;
		}
		for (unsigned int i = 0; i < p[x][y].size(); i++) {
			int nx = p[x][y][i].first.first;
			int ny = p[x][y][i].first.second;
			int nz = p[x][y][i].second;
			if (v[nx][ny]) continue;
			if (nz) {
				if (d[nx][ny] > d[x][y] + 1) {
					d[nx][ny] = d[x][y] + 1;
					q.push_back(make_pair(nx, ny));
				}
			} else {
				if (d[nx][ny] > d[x][y]) {
					q.push_front(make_pair(nx, ny));
					d[nx][ny] = d[x][y];
				}
			}
		}
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) dlwx();
	return 0;
}

Solution

#include <iostream>
#include <string>
#include <deque>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510, M = N * N, INF = 0x3f3f3f3f;
const int dx[4] = {-1, -1, 0, 0}, dy[4] = {-1, 0, -1, 0};
const int posx[4] = {-1, -1, 1, 1}, posy[4] = {-1, 1, -1, 1};

struct pos{
  int x, y;
};

int n, m;
string g[N];
pos q[M];
bool used[N][N];
int dist[N][N];
string op = "\\//\\";


bool valid(int x, int y) {
  return x >= 1 && x <= n && y >= 1 && y <= m;
}

int bfs(pos u) {
  deque<pos> q;
  q.push_back(u);
  dist[u.x][u.y] = 0;
  
  while (q.size()) {
    auto now = q.front(); q.pop_front();
    
    if (used[now.x][now.y]) continue; //已经出队被扩展过，则跳过
    used[now.x][now.y] = true; //标记出队被扩展过
    
    //第一次出队被扩展时，就是最短距离
    if (now.x == n + 1 && now.y == m + 1) break; //已经到达终点
    
    for (int i = 0; i < 4; ++i) {
      int x = now.x + dx[i], y = now.y + dy[i]; //连接线位置
      if (!valid(x, y)) continue;
      
      int px = now.x + posx[i], py = now.y + posy[i]; //坐标点位置
      if (used[px][py]) continue;
      
      int cost = g[x][y] != op[i];
      int d = dist[now.x][now.y] + cost;
      
      if (d < dist[px][py]) { //入队时不一定是最优的，需要判断
        dist[px][py] = d;
        if (cost) q.push_back({px, py});
        else q.push_front({px, py});
      }
    }
  }
  return dist[n + 1][m + 1];
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> g[i], g[i] = " " + g[i];
    
    memset(dist, 0x3f, sizeof dist);
    memset(used, 0, sizeof used);
    int t = bfs({1, 1});
    
    if (t == INF) cout << "NO SOLUTION" << endl;
    else cout << t << endl;
  }
}

---

优先队列BFS

对于更加具有普适性的情况，也就是每次扩展都有各自不同的 “代价” 时，求出起始状态到每个状态的最小代价, 就相当于在一张带权图上求出从起点到每个节点的最短路。此时, 我们有两个解决方案:

方法一

仍然使用一般的广搜, 采用一般的队列。

这时我们不再能保证每个状态第一次入队时就能得到最小代价, 所以只能允许一个状态被多次更新、多次进出队列。我们不断执行搜索, 直到队列为空。

整个广搜算法对搜索树进行了重复遍历与更新, 直至 “收敛” 到最优解, 其实也就是 “迭代” 的思想。最坏情况下, 该算法的时间复杂度会从一般广搜的 $O(N)$ 增长到 $O(N^{2})$ 。对应在最短路问题中, 就是我们介绍的 SPFA 算法。

方法二

改用优先队列进行广搜。 这里的 “优先队列” 就相当于一个二叉堆。我们可以每次从队列中取出当前代价最小的状态进行扩展 (该状态一定已经是最优的, 因为队列中其他状态的当前代价都不小于它, 所以以后就不可能再更新它了), 沿着各条分支把到达的新状态（如果经过当前点扩展到达的状态会比之前更小，则更新入队）加入优先队列。不断执行搜索, 直到队列为空。

在优先队列 BFS 中, 每个状态也会被多次更新、多次进出队列, 一个状态也可能以不同的代价在队列中同时存在。不过, 当每个状态第一次从队列中被取出时, 就得到了从起始状态到该状态的最小代价。之后若再被取出, 则可以直接忽略, 不进行扩展。 所以, 优先队列 BFS 中每个状态只用来扩展一次, 时间复杂度只多了维护二叉堆的代价。若一般广搜复杂度为 $O(N)$, 则优先队列 BFS 的复杂度为 $O(N \log N)$ 。对应在最短路问题中, 就是我们介绍的堆优化的 Dijkstra 算法。

下图就展示了优先队列 BFS 的详细过程, 每条边上的数值标明了每个状态向下扩展所需的代价, 节点中的数值标明了每个状态上求出的 “当前代价”, 灰色节点标明了每个时刻在堆中出现至少一次的节点。

建议不熟悉最短路相关算法的读者，简要最短路中的两个单源最短路径算法进行阅读，这对于理解并写出正确的优先队列BFS 有很大的帮助。

BFS形式总结

至此，我们就可以对BFS 的形式，按照对应在图上的边权情况进行分类总结：

1. 问题只计最少步数, 等价于在边权都为 1 的图上求最短路。

   • 使用普通的 BFS，时间复杂度 $O(N)$ 。
     • 每个状态只访问 (入队) 一次, 第一次入队时即为该状态的最少步数。

2. 问题每次扩展的代价可能是 0 或 1 , 等价于在边权只有 0 和 1 的图上求最短路。

   • 使用双端队列 BFS，时间复杂度 $O(N)$ 。
     • 每个状态被更新（入队）多次，只用来扩展一次，第一次出队时即为该状态的最小代价。

3. 问题每次扩展的代价是任意数值, 等价于一般的最短路问题。

   • 使用优先队列 BFS, 时间复杂度 $O(N \log N)$ 。

     • 每个状态被更新 (入队) 多次, 只用来扩展一次, 第一次出队时即为该状态的最小代价。

   • 使用迭代思想+普通的 BFS, 时间复杂度 $\mathrm{O}\left(N^{2}\right)$ 。

     • 每个状态被更新（入队）和用来扩展（出队）多次, 最终完成搜索后, 记录数组中保存了最小代价。

---

176. 装满的油箱

题目描述

有 $N$ 个城市（编号 $0、1…N-1$）和 $M$ 条道路，构成一张无向图。

在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。

现在你需要回答不超过 $100$ 个问题，在每个问题中，请计算出一架油箱容量为 $C$ 的车子，从起点城市 $S$ 开到终点城市 $E$ 至少要花多少油钱？

注意： 假定车子初始时油箱是空的。

输入格式

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个整数，代表 $N$ 个城市的单位油价，第 $i$ 个数即为第 $i$ 个城市的油价 $p_i$。

接下来 $M$ 行，每行包括三个整数 $u,v,d$，表示城市 $u$ 与城市 $v$ 之间存在道路，且车子从 $u$ 到 $v$ 需要消耗的油量为 $d$。

接下来一行包含一个整数 $q$，代表问题数量。

接下来 $q$ 行，每行包含三个整数 $C、S、E$，分别表示车子油箱容量 $C$、起点城市 $S$、终点城市 $E$。

输出格式

对于每个问题，输出一个整数，表示所需的最少油钱。

如果无法从起点城市开到终点城市，则输出 impossible。

每个结果占一行。

数据范围

$1 \le N \le 1000$,
$1 \le M \le 10000$,
$1 \le p_i \le 100$,
$1 \le d \le 100$,
$1 \le C \le 100$

输入样例：

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4 

输出样例：

170
impossible 

算法分析

我们使用二元组 $(city, fuel)$ 来表示每个状态, 其中 $city$ 为城市编号, $fuel$ 为油箱中剩余的汽油量, 并使用记录数组 $d[ city ][f u e l]$ 存储最少花费。

对于每个问题, 我们都单独进行一次优先队列 $B F S$ 。起始状态为 $(S, 0)$ 。每个状态 $(city, fuel)$ 的分支有:

1. 若 $f u e l<C$, 可以加 1 升油, 扩展到新状态 $(city, fuel + 1)$, 花费在城市 $city$ 加 1 升油的钱。
2. 对于每条从 $city$ 出发的边 $(city,next)$, 若边权大小 $w$ 不超过 $f u e l$, 可以开车前往城市 $next$ , 扩展到新状态 $(next, fuel - w)$。

我们不断取出优先队列中 “当前花费最少” 的状态 (堆顶) 进行扩展, 更新扩展到的新状态在记录数组 $d$ 中存储的值, 直到终点 $T$ 的某个状态第一次被取出, 即可停止 BFS, 输出答案。

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1006, C = 106;
int n, m, p[N], d[N][C];
bool v[N][C];
vector<pair<int, int> > e[N];
priority_queue<pair<int, pair<int, int> > > q;

void Full_Tank() {
	int c, st, ed;
	scanf("%d %d %d", &c, &st, &ed);
	priority_queue<pair<int, pair<int, int> > > empty;
	swap(q, empty);
	memset(d, 0x3f, sizeof(d));
	q.push(make_pair(0, make_pair(st, 0)));
	d[st][0] = 0;
	memset(v, 0, sizeof(v));
	while (q.size()) {
		int city = q.top().second.first;
		int fuel = q.top().second.second;
		q.pop();
		if (city == ed) {
			cout << d[city][fuel] << endl;
			return;
		}
		if (v[city][fuel]) continue;
		v[city][fuel] = 1;
		if (fuel < c && d[city][fuel+1] > d[city][fuel] + p[city]) {
			d[city][fuel+1] = d[city][fuel] + p[city];
			q.push(make_pair(-d[city][fuel] - p[city], make_pair(city, fuel + 1)));
		}
		for (unsigned int i = 0; i < e[city].size(); i++) {
			int y = e[city][i].first, z = e[city][i].second;
			if (z <= fuel && d[y][fuel-z] > d[city][fuel]) {
				d[y][fuel-z] = d[city][fuel];
				q.push(make_pair(-d[city][fuel], make_pair(y, fuel - z)));
			}
		}
	}
	cout << "impossible" << endl;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) scanf("%d", &p[i]);
	for (int i = 1; i <= m; i++) {
		int u, v, d;
		scanf("%d %d %d", &u, &v, &d);
		e[u].push_back(make_pair(v, d));
		e[v].push_back(make_pair(u, d));
	}
	int q;
	cin >> q;
	while (q--) Full_Tank();
	return 0;
}

Solution

---

双向BFS

在迭代加深与双向搜索 中我们介绍了双向搜索的思想, 并讲解了一道双向 DFS 的例题。双向 BFS 的思想与之完全相同, 我们就不再重复描述。因为 BFS 本身就是逐层搜索的算法, 所以双向 BFS 的实现更加自然、简便。以普通的求最少步数的双向 BFS 为例, 我们只需从起始状态、目标状态分别开始, 两边轮流进行, 每次各扩展一整层。当两边各自有一个状态在记录数组中发生重复时, 就说明这两个搜索过程相遇了，可以合并得出起点到终点的最少步数。

---

177. 噩梦

题目描述

给定一张 $N \times M$ 的地图，地图中有 $1$ 个男孩，$1$ 个女孩和 $2$ 个鬼。

字符 . 表示道路，字符 X 表示墙，字符 M 表示男孩的位置，字符 G 表示女孩的位置，字符 Z 表示鬼的位置。

男孩每秒可以移动 $3$ 个单位距离，女孩每秒可以移动 $1$ 个单位距离，男孩和女孩只能朝上下左右四个方向移动。

每个鬼占据的区域每秒可以向四周扩张 $2$ 个单位距离，并且无视墙的阻挡，也就是在第 $k$ 秒后所有与鬼的曼哈顿距离不超过 $2k$ 的位置都会被鬼占领。

注意： 每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。

求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试用例。

每组测试用例第一行包含两个整数 $N$ 和 $M$，表示地图的尺寸。

接下来 $N$ 行每行 $M$ 个字符，用来描绘整张地图的状况。（注意：地图中一定有且仅有 $1$ 个男孩，$1$ 个女孩和 $2$ 个鬼）

输出格式

每个测试用例输出一个整数 $S$，表示最短会合时间。

如果无法会合则输出 $-1$。

每个结果占一行。

数据范围

$1 < n,m < 800$

输入样例：

3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X 

输出样例：

1
1
-1 

算法分析

使用双向 BFS 算法。建立两个队列, 分别从男孩的初始位置、女孩的初始位置开始进行 BFS, 两边轮流进行。

在每一轮中, 男孩这边 $\mathrm{BFS}$ 三层 (可以移动三步), 女孩这边 $\mathrm{BFS}$ 一层 (可以移动一步), 使用数组 $d$ 记录每个位置对于男孩和女孩的可达性。

当然, 在 BFS 的每次扩展时, 注意实时计算新状态与鬼之间的曼哈顿距离, 如果已经小于等于当前轮数 (即秒数) 的 2 倍, 那么就判定这个新状态不合法, 不再记录或入队。

在 BFS 的过程中, 第一次出现某个位置 $(x, y)$ 既能被男孩到达, 也能被女孩到达时, 当前轮数就是两人的最短会合时间。

#include <queue>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 806;
char s[N][N];
bool v1[N][N], v2[N][N];
int n, m, bx, by, gx, gy, px, py, qx, qy, s1, s2;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

bool pd(int x, int y, int k) {
	if (x <= 0 || x > n || y <= 0 || y > m) return 0;
	if (abs(x - px) + abs(y - py) <= 2 * k) return 0;
	if (abs(x - qx) + abs(y - qy) <= 2 * k) return 0;
	if (s[x][y] == 'X') return 0;
	return 1;
}

int bfs() {
	queue<pair<int, int> > q1, q2;
	px = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == 'M') {
				bx = i;
				by = j;
			} else if (s[i][j] == 'G') {
				gx = i;
				gy = j;
			} else if (s[i][j] == 'Z') {
				if (!px) {
					px = i;
					py = j;
				} else {
					qx = i;
					qy = j;
				}
			}
	int ans = 0;
	memset(v1, 0, sizeof(v1));
	memset(v2, 0, sizeof(v2));
	v1[bx][by] = 1;
	v2[gx][gy] = 1;
	q1.push(make_pair(bx, by));
	q2.push(make_pair(gx, gy));
	while (q1.size() || q2.size()) {
		ans++;
		s1 = q1.size();
		for (int i = 1; i <= s1; i++) {
			pair<int, int> now = q1.front();
			q1.pop();
			if (!pd(now.first,now.second,ans)) continue;
			for (int j = 0; j < 4; j++) {
				int nx = now.first + dx[j];
				int ny = now.second + dy[j];
				if (pd(nx,ny,ans) && !v1[nx][ny]) {
					v1[nx][ny] = 1;
					q1.push(make_pair(nx, ny));
				}
			}
		}
		s1 = q1.size();
		for (int i = 1; i <= s1; i++) {
			pair<int, int> now = q1.front();
			q1.pop();
			if (!pd(now.first,now.second,ans)) continue;
			for (int j = 0; j < 4; j++) {
				int nx = now.first + dx[j];
				int ny = now.second + dy[j];
				if (pd(nx,ny,ans) && !v1[nx][ny]) {
					v1[nx][ny] = 1;
					q1.push(make_pair(nx, ny));
				}
			}
		}
		s1 = q1.size();
		for (int i = 1; i <= s1; i++) {
			pair<int, int> now = q1.front();
			q1.pop();
			if (!pd(now.first,now.second,ans)) continue;
			for (int j = 0; j < 4; j++) {
				int nx = now.first + dx[j];
				int ny = now.second + dy[j];
				if (pd(nx,ny,ans) && !v1[nx][ny]) {
					v1[nx][ny] = 1;
					q1.push(make_pair(nx, ny));
				}
			}
		}
		s2 = q2.size();
		for (int i = 1; i <= s2; i++) {
			pair<int, int> now = q2.front();
			q2.pop();
			if (!pd(now.first,now.second,ans)) continue;
			for (int j = 0; j < 4; j++) {
				int nx = now.first + dx[j];
				int ny = now.second + dy[j];
				if (pd(nx,ny,ans) && !v2[nx][ny]) {
					if (v1[nx][ny]) return ans;
					v2[nx][ny] = 1;
					q2.push(make_pair(nx, ny));
				}
			}
		}
	}
	return -1;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
			scanf("%s", s[i] + 1);
		cout << bfs() << endl;
	}
	return 0;
}

Solution

---

190. 字串变换

题目描述

已知有两个字串 $A$, $B$ 及一组字串变换的规则（至多 $6$ 个规则）:

$A_1 \to B_1$

$A_2 \to B_2$

…

规则的含义为：在 $A$ 中的子串 $A_1$ 可以变换为 $B_1$、$A_2$ 可以变换为 $B_2…$。

例如：$A$＝abcd $B$＝xyz

变换规则为：

abc $\to$ xu ud $\to$ y y $\to$ yz

则此时，$A$ 可以经过一系列的变换变为 $B$，其变换的过程为：

abcd $\to$ xud $\to$ xy $\to$ xyz

共进行了三次变换，使得 $A$ 变换为 $B$。

输入格式

输入格式如下：

$A$ $B$
$A_1$ $B_1$
$A_2$ $B_2$
… …

第一行是两个给定的字符串 $A$ 和 $B$。

接下来若干行，每行描述一组字串变换的规则。

所有字符串长度的上限为 $20$。

输出格式

若在 $10$ 步（包含 $10$ 步）以内能将 $A$ 变换为 $B$ ，则输出最少的变换步数；否则输出 NO ANSWER!。

输入样例：

abcd xyz
abc xu
ud y
y yz 

输出样例：

3 

算法分析

(BFS,双向BFS) $O((LN)^5)$

假设每次决策数量是 $K$，那么如果直接BFS，最坏情况下的搜索空间是 $K^{10}$，非常大，所以会TLE或者MLE。

如果采用双向BFS，则可以把搜索空间降到 $2K^5$。在实际测试中只需 20ms 左右，剪枝效果很好。

BFS的扩展方式是：分别枚举在原字符串中使用替换规则的起点，和所使用的的替换规则。

双向BFS的基本实现思路如下：

1. 创建「两个队列」分别用于两个方向的搜索；
2. 创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
3. 为了尽可能让两个搜索方向“平均”，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
4. 如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。

//q1、q2 为两个方向的队列
//m1、m2 为两个方向的哈希表，记录每个节点到起点的距离

//extend 为从队列 d 中取出一层元素进行「扩展一层」的逻辑
void extend(queue &d, Map &cur, Map &other) {}

// 只有两个队列都不空，才有必要继续往下搜索
// 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
while(q1.size() && q2.size()) {
    if (q1.size() < q2.size()) {
        extend(q1, m1, m2);
    } else {
        extend(d2, m2, m1);
    }
}

时间复杂度

假设字符串长度是 $L$，替换规则一共有 $N$ 个，则：

在最坏情况下每次会从字符串的每个位置开始，使用全部的 $N$ 种替换规则，因此总共会有 $LN$ 种扩展方式，从起点和终点最多会分别扩展5步，因此总搜索空间是 $2(LN)^5$。

在BFS过程中，空间中的每个状态只会被遍历一次，因此时间复杂度是 $O((LN)^5)$。

Solution

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

const int N = 10;

int n;
string A, B;
string a[N], b[N];

int extend(queue<string> &qst, unordered_map<string, int> &dst, unordered_map<string, int> ded, string a[], string b[]) {
  int d = dst[qst.front()];
  while (qst.size() && dst[qst.front()] == d) { //完整扩展一层 
    auto now = qst.front(); qst.pop();
    for (int i = 0; i < now.size(); ++i) {
      for (int j = 0; j < n; ++j) {
        int len = a[j].size();
        if (now.substr(i, len) == a[j]) {
          string next = now.substr(0, i) + b[j] + now.substr(i + len);
          
          if (ded.count(next)) return dst[now] + 1 + ded[next];
          
          if (dst.count(next)) continue;
          qst.push(next);
          dst[next] = dst[now] + 1;
        }
      }
    }
  }
  return 11;
}

int bfs(string &st, string &ed){
  if (st == ed) return 0;
  
  queue<string> qst, qed;
  unordered_map<string, int> dst, ded;
  qst.push(st), dst[st] = 0;
  qed.push(ed), ded[ed] = 0;
  
  int step = 0;
  while (qst.size() && qed.size()) {
    int t;
    if (qst.size() < qed.size()) t = extend(qst, dst, ded, a, b);
    else t = extend(qed, ded, dst, b, a);

    if (t <= 10) return t;
    if (++step >= 10) break;
  }

  return 11;
}

int main() {
  cin >> A >> B;
  while (cin >> a[n] >> b[n]) ++n;
  
  int step = bfs(A, B);

  if (step <= 10) cout << step;
  else cout << "NO ANSWER!";
}