洛谷 P1032 字串变换(map)

题目传送门

解题思路:

搜索题,因为要求最少次数,用bfs.

AC代码:

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring> 
 4 #include<string>
 5 #include<queue>
 6 #include<map>
 7 
 8 using namespace std;
 9 
10 string a,b,ca[7],cb[7];
11 int l;
12 queue<string> q;
13 queue<int> q1;
14 map<string,bool> aa;
15 
16 inline void _read() {
17     cin >> a >> b;
18     for(int i = 1;i <= 6; i++)
19         cin >> ca[i] >> cb[i];
20     l = 6;
21     while(ca[l][0] == '') l--;
22     if (l == 0 && a != b) {
23         cout << "NO ANSWER!";
24         return ;
25     }
26     q.push(a);
27     q1.push(0);
28 }
29 
30 inline void bfs() {
31     string pp,oo;
32     int m = 0;
33     while(!q.empty() && q1.front() <= 10 && q.front()!=b) {
34         pp = q.front();
35         if(aa[pp]) {
36             q.pop();
37             q1.pop();
38             continue;
39         }
40         aa[pp] = 1;
41         for(int i = 1;i <= l; i++) {
42             while(true) {
43                 m = pp.find(ca[i]);
44                 if(m == -1) break;
45                 oo = pp;
46                 oo.replace(m,ca[i].size(),cb[i]);
47                 q.push(oo);
48                 q1.push(q1.front() + 1);
49                 pp[m] = '%';
50             }
51         }
52         q.pop();
53         q1.pop();
54     }
55 }
56 
57 inline void panduan_and_print() {
58     if(q1.front() > 10) {
59         printf("NO ANSWER!");
60         return ;
61     }
62     if(q.empty()) {
63         printf("NO ANSWER!");
64         return ;
65     }
66     printf("%d",q1.front());
67 }
68 
69 int main()
70 {
71     _read();
72     bfs();
73     panduan_and_print();
74     return 0;
75 }

40分

//一开始40分,错误在bfs过程中oo和pp的值处理不对

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring> 
 4 #include<string>
 5 #include<queue>
 6 #include<map>
 7 
 8 using namespace std;
 9 
10 string a,b,ca[7],cb[7];
11 int l;
12 queue<string> q;
13 queue<int> q1;
14 map<string,int> aa;
15 
16 inline void _read() {
17     cin >> a >> b;
18     for(int i = 1;i <= 6; i++)
19         cin >> ca[i] >> cb[i];
20     l = 6;
21     while(ca[l][0] == '') l--;
22     if (l == 0 && a != b) {
23         cout << "NO ANSWER!";
24         return ;
25     }
26     q.push(a);
27     q1.push(0);
28 }
29 
30 inline void bfs() {
31     string pp,oo;
32     int m = 0;
33     while(!q.empty() && q1.front() <= 10 && q.front()!=b) {
34         if(aa[q.front()] == 1) {
35             q.pop();
36             q1.pop();
37             continue;
38         }
39         aa[q.front()] = 1;
40         for(int i = 1;i <= l; i++) {
41             pp = q.front();
42             while(true) {
43                 m = pp.find(ca[i]);
44                 if(m == -1) break;
45                 oo = q.front();
46                 oo.replace(m,ca[i].size(),cb[i]);
47                 q.push(oo);
48                 q1.push(q1.front() + 1);
49                 pp[m] = '~';//将S里子串sa[i]的第一次出现位置随便换成另一种无关的字符,这样就可以查找到S里子串sa[i]的下一个出现位置
50             }
51         }
52         q.pop();
53         q1.pop();
54     }
55 }
56 
57 inline void panduan_and_print() {
58     if(q1.front() > 10) {
59         printf("NO ANSWER!");
60         return ;
61     }
62     if(q.empty()) {
63         printf("NO ANSWER!");
64         return ;
65     }
66     printf("%d",q1.front());
67 }
68 
69 int main()
70 {
71     _read();
72     bfs();
73     panduan_and_print();
74     return 0;
75 }

100分