AcWing 190. 字串变换

原题连接：AcWing 190. 字串变换

题意：

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

(A_1→B_1)
(A_2→B_2)
(…)

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

例如：(A＝abcd \,\,\, B＝xyz)

变换规则为：

(abc → xu \,\,\,\, ud → y \,\,\,\, y → yz)

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

(abcd → xud → xy → xyz)

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

输入格式

输入格式如下：

(A \,\,\, B)
(A_1 \,\,\, B_1)
(A_2 \,\,\, B_2)
… …

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

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

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

输出格式

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

双向BFS：

从起始状态，目标状态分别开始，两边轮流进行，每次扩展数量小的那一层（即队列中元素数小的那一层），扩展一层，当两边各自一个状态在记录数组中发生重复时，就说明两个搜索过程相遇了，可以合并得到起点的最小步数。

// Problem: 字串变换
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/192/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

const int N = 6;

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

int extend(queue<string> &q, unordered_map<string, int> &da, unordered_map<string, int> &db, string a[], string b[]) {
	int SZ = q.size();
	while (SZ--) {
		auto t = q.front();
		q.pop();
		
		for (int i = 0; i < t.size(); i++) { //枚举字符串起点
			for (int j = 0; j < n; j++) { 
				if (t.substr(i, a[j].size()) == a[j]) {
					string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size());
					if (da.count(state)) continue;
					if (db.count(state)) return da[t] + 1 + db[state];
					da[state] = da[t] + 1;
					q.push(state);
				}
			}
		}
	}
	
	return 11;
}

int bfs(string A, string B) {
	unordered_map<string, int> da, db;
	queue<string> qa, qb;
	qa.push(A);
	qb.push(B);
	da[A] = 0, db[B] = 0;
	
	while (qa.size() && qb.size()) {
		int t;
		
		if (qa.size() <= qb.size())t = extend(qa, da, db, a, b); //先搜少的那个集合
		else t = extend(qb, db, da, b, a);
		
		if (t <= 10) return t;
	}
	
	return 11;
}

int main() {
    string A, B;
	cin >> A >> B;
	while (cin >> a[n] >> b[n]) n++;
	
	int step = bfs(A, B);
	if (step > 10) puts("NO ANSWER!");
	else cout << step << endl;
	
    return 0;
}