河北网站建设,外贸网站建设模版,关于幼儿建设网站ppt模板,北京网站编程培训65. [NOIP2002] 字串变换 ★★ 输入文件#xff1a;string.in 输出文件#xff1a;string.out 简单对比时间限制#xff1a;1 s 内存限制#xff1a;128 MB [问题描述] 已知有两个字串A\$, B\$及一组字串变换的规则#xff08;至多6个规则#xff09;: A1\$ -string.in 输出文件string.out 简单对比时间限制1 s 内存限制128 MB [问题描述] 已知有两个字串A\$, B\$及一组字串变换的规则至多6个规则: A1\$ - B1\$ A2\$ - B2\$ 规则的含义为在A\$中的子串A1\$可以变换为B1\$、A2\$可以变换为B2\$…。 例如A\$abcd B\$xyz 变换规则为‘abc’-‘xu’ ‘ud’-‘y’ ‘y’-‘yz’ 则此时A\$可以经过一系列的变换变为B\$其变换的过程为 ‘abcd’-‘xud’-‘xy’-‘xyz’ 共进行了三次变换使得A$变换为B$。 [输入] A\$ B\$ A1\$ B1\$ A2\$ B2\$ |-变换规则 ... ... / 所有字符串长度的上限为20。 [输出] 若在10步包含10步以内能将A\$变换为B\$则输出最少的变换步数否则输出NO ANSWER! [输入样例] abcd xyz
abc xu
ud y
y yz[输出样例] 3 依然是大力暴搜... 单向 $BFS$ 的话开一个队列, 先把原串怼进去, 然后每次取队首字符串并尝试应用变换规则. 每应用成功一个变换后将变换后的字符串再怼回队列里. 一直重复直至变换得到待求串或者队列为空. 如果队列为空则说明不存在解. 用 $STL$ 里的 $std::string,std::pair,std::map$ 食用即可. 双向 $BFS$ 的话就从两端对称搜索, 但是深度限制在 $10$ 以内可能并不会显得多快OwO... 附双向 $BFS$ 的参考实现: GitHub 1 #include set2 #include map3 #include queue4 #include cstdio5 #include string6 #include cstring7 #include cstdlib8 #include iostream9 #include algorithm
10
11 typedef std::pairstd::string,int pr;
12
13 int n;
14 int m;
15 int ans;
16 std::string from,to;
17 std::queuepr q1,q2;
18 std::string transform[10][2];
19 std::mapstd::string,int m1,m2;
20 std::pairstd::string,int p1,p2;
21
22 bool Search();
23 void Initialize();
24 std::string Replace(std::string,int,int,std::string);
25
26 int main(){
27 Initialize();
28 if(Search())
29 std::coutansstd::endl;
30 else
31 std::coutNO ANSWER!std::endl;
32 return 0;
33 }
34
35 bool Search(){
36 int len,lenp;
37 while((!q1.empty())(!q2.empty())){
38 p1q1.front();
39 lenp1.first.size();
40 for(int i0;ilen;i){
41 for(int j0;jm;j){
42 lenptransform[j][0].size();
43 if(ilenplenp1.first.compare(i,lenp,transform[j][0])0m1.count(Replace(p1.first,i,lenp,transform[j][1]))0){
44 p2.firstReplace(p1.first,i,lenp,transform[j][1]);
45 p2.secondq1.front().second1;
46 if(p2.second10)
47 return false;
48 m1[p2.first]p2.second;
49 q1.push(p2);
50 if(m2.count(p2.first)){
51 ansp2.secondm2[p2.first];
52 return true;
53 }
54 }
55 }
56 }
57 q1.pop();
58 p1q2.front();
59 lenp1.first.size();
60 for(int i0;ilen;i){
61 for(int j0;jm;j){
62 lenptransform[j][1].size();
63 if(ilenplenp1.first.compare(i,lenp,transform[j][1])0m2.count(Replace(p1.first,i,lenp,transform[j][0]))0){
64 p2.firstReplace(p1.first,i,lenp,transform[j][0]);
65 p2.secondq2.front().second1;
66 if(p2.second10)
67 return false;
68 m2[p2.first]p2.second;
69 q2.push(p2);
70 if(m1.count(p2.first)){
71 ansp2.secondm1[p2.first];
72 return true;
73 }
74 }
75 }
76 }
77 q2.pop();
78 }
79 return false;
80 }
81
82 void Initialize(){
83 std::ios::sync_with_stdio(false);
84 std::cin.tie(0);
85 std::cinfromto;
86 while(std::cintransform[m][0]transform[m][1])
87 m;
88 m1[from]0;
89 m2[to]0;
90 q1.push(std::make_pair(from,0));
91 q2.push(std::make_pair(to,0));
92 }
93
94 inline std::string Replace(std::string s, int pos,int len,std::string p){
95 return s.replace(pos,len,p);
96 } Backup 转载于:https://www.cnblogs.com/rvalue/p/7308487.html
