https://www.luogu.com.cn/problem/P1032

题意：字串 A B, 存在一些转换规则使得子串由 A’ -> B’ ，问最少的转换步数。超过 10 步，输出 “NO ANSWER!”
输入输出样例
输入
abcd xyz
abc xu
ud y
y yz
输出
3

双向 bfs , 有几个字符串的坑…
有相同的多个子串时，每次只转换一个子串，因为有多种选择每个都要试一遍。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d",n)
#define pfc(c) printf(c)
#define fi(i,s,t) for(int i=s;i<t;i++)
#define fd(s,t) for(int i=s-1;i>=t;i--)
#define mem(a,c) memset(a,c,sizeof(a))
const int INF=0x3f3f3f3f;
string a,b,c[10],d[10];
map<string,int> m,len; //vis
queue<string> s;
queue<string> t;
int cnt=0,L[30];
int count(string a,string b){ //num of b in a
	int cnt=0;
	int len = b.size(),l = a.find(b);
	while(l!=-1){
		L[cnt++]=l;
		l=a.find(b,l+len);
	}
	return cnt;
}
string _replace(int index,string a,string b,string c){
	int len = b.size();
	a.replace(index,len,c);
	return a;
}
int bfs(){
//	queue<string> s;
//	queue<string> t;
	if(!a.compare(b)) {
		return 0;
	}
	s.push(a);m[a]=1;
	t.push(b);m[b]=2;
	while(!s.empty() || !t.empty()){
		if(!s.empty()){
			string tmp= s.front();
			s.pop();
			fi(i,0,cnt){
				int l= count(tmp,c[i]);
				fi(j,0,l){
					string tmp2= _replace(L[j],tmp,c[i],d[i]);
					if(tmp2.compare(tmp)!=0){
						if(m[tmp2]==0){
							len[tmp2] = len[tmp] +1 ;
							if(len[tmp2]>10) continue; // 10 steps
							m[tmp2]=1;
							s.push(tmp2);
						} else if(m[tmp2]==2){
							return len[tmp2] + len[tmp] +1;
						}
					}
				}
			}
		}
		if(!t.empty()){
			string tmp= t.front();
			t.pop();
			fi(i,0,cnt){
				int l= count(tmp,d[i]);
				fi(j,0,l){
					string tmp2= _replace(L[j],tmp,d[i],c[i]);
					if(tmp2.compare(tmp)!=0){
						if(m[tmp2]==0){
							len[tmp2] = len[tmp] +1 ;
							if(len[tmp2]>10)continue;
							m[tmp2]=2; 
							t.push(tmp2);
						} else if(m[tmp2]==1) {
							return len[tmp2] + len[tmp] +1;
						}
					}
				}
			}
		}
	}
	return -1;
}
int main(){
	freopen("in","r",stdin);
	cin>>a>>b;
	while(cin>>c[cnt]>>d[cnt]) cnt++;
	int t=bfs();
	if(t>-1) cout<<t;
	else cout<<"NO ANSWER!";
	return 0;
}

补一个 c++ 字符串替换函数，本题没用

1
2
3
4
5
6
7
8
9
10
11
12
string _replace(string a,string b,string c){//replace all b in a
	int len1 = b.size(),len2=c.size(),l = a.find(b),L[100],cnt=0;
	while(l!=-1){
		L[cnt++]=l;
		l = a.find(b,l+len1);
	}
	for(int i=0;i<cnt;i++){
		int inc= i>0? i * (len2-len1):0;
		a.replace(L[i] + inc ,len1,c);
	}
	return a;
}