题解 | #[NOIP2002]字串变换#

#include<iostream>
#include<math.h>
#include<vector>         
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<unordered_map>
using namespace std;
const int N =2e5+10;
typedef long long ll;
typedef unordered_map<string, int> und;
string aq[7], bw[7];
int _1=0;
string a, b;
int replace_charctor(queue<string>& q, und& nowd, und& red, string now[], string re[])
{
	string s = q.front();
	q.pop();
	for (int i = 0;i < s.size();i++)//枚举当前字符的位置
	{
		for (int j = 0;j < _1;j++) {
			if (s.substr(i, now[j].size()) == now[j])
			{
				string str = s.substr(0, i) + re[j] + s.substr(i + now[j].size());//替换大法
				if (nowd.count(str))continue;//已经替换过了捏！这条路走过了
				if (red.count(str))return nowd[s] + 1 + red[str];//在反向队列里面出现过！返回
				nowd[str] = nowd[s] + 1;
				q.push(str);
			}

		}
	}
	return 99;
}
	int bfs()
	{
		und da, db;//绑定键值
		queue<string>qa, qb;
		int t;//答案捏
		qa.push(a);da[a] = 0;
		qb.push(b);db[b] = 0;
		while (!qa.empty() && !qb.empty())//一方为空说明该方向无法连通,无法拓展下层元素
		{
			if (qa.size() < qb.size())t = replace_charctor(qa, da, db, aq, bw);//这里是广搜的优化用状态少的一方进行拓展
			else t = replace_charctor(qb, db, da, bw, aq);
			if (t <=10)return t;
		}
		return 99;
	}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >>a>> b;
	if (a==b) { cout << 0 << endl; return 0;}
	while (cin >> aq[_1] >> bw[_1])_1++;
	int t=bfs();
	if (t > 10)cout << "NO ANSWER!";
	else cout << t;
	return 0;
}

#include<iostream>
#include<math.h>
#include<vector>         
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<unordered_map>
using namespace std;
string a,b;
int ans=1e9;
int cur;
string s[10], t[10];
void dfs(string u,int cnt)
{
    if(cnt>10||cnt>=ans)return;
    if(u==b){ans=min(ans,cnt);return;}
        for (int i = 0; i < cur - 1; ++ i){
        int p = u.find(s[i]);
        if (p == -1) continue;
        u.replace(p, s[i].size(), t[i]);
        dfs(u, cnt + 1);
        p = u.find(t[i]);
        u.replace(p, t[i].size(), s[i]);
    }
}
int main()
{
    cin>>a>>b;
    string A,B;
    while (cin >> s[cur] >> t[cur ++ ]);
    dfs(a,0);
    if (ans > 10) cout << "NO ANSWER!";
    else cout << ans;
    return 0;
}