C++(g++ 7.5.0) 解法, 执行用时: 497ms, 内存消耗: 428K, 提交时间: 2023-06-23 17:08:16

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int res=1007;
int tot=1;

string st,ed;
string a[107],b[107];

void dfs(string str,int cnt){
	if(cnt>10||cnt>=res) return ;
	if(str==ed){
		res=min(res,cnt);
		return ;
	}
	
	for(int i=1;i<=tot;i++){
		int p=str.find(a[i]);
		if(p==-1) continue;
		str.replace(p,a[i].size(),b[i]);
		dfs(str,cnt+1);
		p=str.find(b[i]);
		str.replace(p,b[i].size(),a[i]); 
	}
}

int main(){
	cin>>st>>ed;
	while(cin>>a[tot]>>b[tot]) tot++;
	tot--;
	dfs(st,0);
	if(res>10) cout<<"NO ANSWER!";
	else cout<<res;
}

C++(clang++ 11.0.1) 解法, 执行用时: 444ms, 内存消耗: 456K, 提交时间: 2022-08-08 16:00:40

#include <bits/stdc++.h>
using namespace std;
int cur, res = INT_MAX;
string a, b;
string s[10], t[10];
void dfs(string u, int cnt){
	if (cnt > 10 || cnt >= res) return;
	if (b == u){
		res = min(cnt, res);
		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;
	while (cin >> s[cur] >> t[cur ++ ]);
	dfs(a, 0);
	if (res > 10) cout << "NO ANSWER!";
	else cout << res;
	return 0;
}