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;
}