[NOIP2002 提高组] 字串变换 题解

前言

双向广搜的代码又臭又长。

讲解

思路

看数据范围，显然普通爆搜（应该）是不能过的，那么我们在这个基础上优化。不难想到，优化可以是把普通广搜改成双向广搜，即从两头搜。

那么，什么是双向广搜？

双向广搜，就是在已知搜的起点和搜的终点是什么，要让你求步数或其他啥的对广搜的优化。双向广搜字面意思，就是从起点和终点两头一起搜，用到两个队列。如果搜到一起了，那么就是通的，也就是最短路径（因为是广搜嘛）。如果一直到两个队列一个空了，那么有一边没路了。

就比如走迷宫，在确定终点和起点在哪里的情况下，两边正常广搜，可以共用一个标记数组，也可以用两个分开的数组。如果撞在一起了，那么这个迷宫是通的，如果你想输出步数，用数组来记录一下也可以。如果两边队列有一个空了，那说明这个迷宫走不通。

这个题也是用双向广搜，从初始字符串和终点字符串两边搜，初始字符串那边因为是顺着搜，所以就按照正常的变换方式；终点字符串那边因为是倒着搜，所以就按照变换方式相反的方式变，也可以说把 $\texttt{→}$ 符号变成 $\texttt{←}$ 符号。

代码

别抄，代码风格难看，且一堆 debug。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main(){
	string a,b;
	cin >> a >> b;
	if (a==b){
		cout<<0<<endl;
		return 0;
	}
	vector<pair<string,string>> q;
	string ai,bi;
	while (cin >> ai >> bi){
		q.emplace_back(ai,bi);
	}
	queue<string> q1,q2;
	q1.emplace(a),q2.emplace(b);
	unordered_map<string,int> n;
	unordered_map<string,bool> f1,f2;
	f1[a]=f2[b]=true;
	n[a]=n[b]=0;
	while (!q1.empty() && !q2.empty()){
		string str1=q1.front(),str2=q2.front(); 
//		cout<<str1<<" "<<str2<<endl;
		q1.pop(),q2.pop();
		for (const auto &item : q){
			string s1=str1,s2=str2;
//			cout<<s1<<" "<<s2<<endl;
			int w1=str1.find(item.first),w2=str2.find(item.second);
			while (w1!=string::npos){
				s1=str1;
				s1.erase(w1,item.first.size());
				s1.insert(w1,item.second);
				w1=str1.find(item.first,w1+1);
				if (f1[s1]){
					continue;
				}
				q1.emplace(s1);
				if (f2[s1]){//之前反向搜的时候搜过了
					if (str1!=s1){//如果两个是错着的形态
						cout<<n[str1]+n[s1]+1<<endl;
					}else{//如果两个是刚好交接的形态
						cout<<n[str1]+n[s1]<<endl;
					}
					return 0;
				}
				f1[s1]=true;
				n[s1]=n[str1]+1;
			}
			while (w2!=string::npos){
				s2=str2;
				s2.erase(w2,item.second.size());
				s2.insert(w2,item.first);
				w2=str2.find(item.second,w2+item.second.size());
				if (f2[s2]){
					continue;
				}
				q2.emplace(s2);
				if (f1[s2]){//刚刚正向搜搜到了 
//					cout<<str2<<' '<<s2<<endl;
					if (str2!=s2){//如果两个是交错的形态
						cout<<n[str2]+n[s2]+1<<endl;
					}else{//如果两个是刚好贴着的形态
						cout<<n[str2]+n[s2]<<endl;
					}
					return 0;
				}
				f2[s2]=true;
				n[s2]=n[str2]+1;
			}
		}
	}
	cout<<"NO ANSWER!"<<endl;
	return 0;
}