华师一附中OI组

标题: P1032 字串变换 [打印本页]

---

作者: admin    时间: 2018-5-11 19:41
标题: P1032 字串变换
https://www.luogu.org/problemnew/show/P1032

题目描述
已知有两个字串 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!"

输入输出样例
输入样例#1：
abcd xyz
abc xu
ud y
y yz
输出样例#1：
3

---

作者: 黄煦喆    时间: 2018-6-9 20:39
80分

1. #include<iostream>
   
2. #include<queue>
   
3. using namespace std;
   
4. string s1[10],s2[10];
   
5. string a,b,p1,p2;
   
6. struct st
   
7. {
   
8.     string s;
   
9.     int step;
   
10. } f[1000001];
    
11. queue<st>q;
    
12. int main()
    
13. {
    
14.     cin>>a>>b;
    
15.     int n=1;
    
16.     while(cin>>p1>>p2)
    
17.     {
    
18.         s1[n]=p1;
    
19.         s2[n]=p2;
    
20.         n++;
    
21.     }
    
22.     f[1].s=a;
    
23.     f[1].step=0;
    
24.     q.push(f[1]);
    
25.     while(q.size())
    
26.     {
    
27.         st t=q.front();
    
28.         q.pop();
    
29.         if(t.s==b)
    
30.         {
    
31.             cout<<t.step;
    
32.             return 0;
    
33.         }
    
34.         else for(int i=1; i<=n; i++)
    
35.             {
    
36.                 int r=t.s.find(s1[i]);
    
37.                 if(r!=-1)
    
38.                 {
    
39.                     st m=t;
    
40.                     m.step++;
    
41.                     if(m.step>10)
    
42.                     {
    
43.                         cout<<"NO ANSWER!";
    
44.                         return 0;
    
45.                     }
    
46.                     m.s.erase(r,s1[i].size());
    
47.                     m.s.insert(r,s2[i]);
    
48.                     q.push(m);
    
49.                 }
    
50.             }
    
51.     }
    
52.     return 0;
    
53. }
    

复制代码

---

作者: admin    时间: 2018-6-9 20:59
很好 能够这样，不错了！

---

作者: YTC    时间: 2018-7-3 19:19

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. string st,en;
   
4. string s1[10],s2[10];
   
5. int cnt=1;
   
6. bool ju(string s,int l,string s1)
   
7. {
   
8.     if(l+s1.size()>s.size()) return 0;
   
9.     if(s.substr(l,s1.size())==s1) return 1;
   
10.     else return 0;
    
11. }
    
12. queue<string> q;
    
13. set<string> ss;
    
14. map<string,int> d;
    
15. int main()
    
16. {
    
17.     cin>>st>>en;
    
18.     while(cin>>s1[cnt]>>s2[cnt]) cnt++;
    
19.     cnt--;
    
20.     q.push(st);
    
21.     ss.insert(st);
    
22.     d[st]=0;
    
23.     while(!q.empty())
    
24.     {
    
25.         string u=q.front();
    
26.         q.pop();
    
27.         if(u==en) {cout<<d[u];return 0;}
    
28.         for(int i=1;i<=cnt;i++)
    
29.             for(int j=0;j+s1[i].size()<=u.size();j++)
    
30.         {
    
31.             if(ju(u,j,s1[i]))
    
32.             {
    
33.                 string s=u.substr(0,j)+s2[i]+u.substr(j+s1[i].size(),u.size()-(j+s1[i].size())+1);
    
34.                 if(!ss.count(s))
    
35.                 {
    
36.                     d[s]=d[u]+1;
    
37.                     if(d[s]<=10)
    
38.                     {
    
39.                         ss.insert(s);
    
40.                         q.push(s);
    
41.                     }
    
42.                 }
    
43.             }
    
44.         }
    
45.     }
    
46.     cout<<"NO ANSWER!";
    
47.     return 0;
    
48. }
    

复制代码

---

作者: YTC    时间: 2018-7-3 19:19

1. 
   

复制代码

---

作者: 倚窗倾听风吹雨    时间: 2018-9-9 15:23

1. #include<iostream>
   
2. #include<queue>
   
3. #include<map>
   
4. using namespace std;
   
5. string s2,s[7][2],k;
   
6. int num,as;
   
7. struct node
   
8. {
   
9.     int step;
   
10.     string s1;
    
11. }p;
    
12. map<string,int>b;
    
13. queue<node>q;
    
14. int main()
    
15. {
    
16.     cin>>p.s1>>s2;
    
17.     int j=1;
    
18.     while(cin>>s[j][0]>>s[j][1])
    
19.     {
    
20.         j++;
    
21.         num++;
    
22.     }
    
23.     p.step=0;
    
24.     q.push(p);
    
25.     while(q.front().step<=10 && !q.empty())
    
26.     {
    
27.         if(b[q.front().s1]==1)
    
28.         {
    
29.             q.pop();
    
30.             continue;
    
31.         }
    
32.         b[q.front().s1]=1;
    
33.         if(q.front().s1==s2)
    
34.         {
    
35.             cout<<q.front().step<<endl;
    
36.             return 0;
    
37.         }
    
38.         for(int i=1;i<=num;i++)
    
39.         {
    
40.             k=q.front().s1;
    
41.             as=k.find(s[i][0]);
    
42.             while(as!=-1)
    
43.             {
    
44.                 j=as;
    
45.                 p.step=q.front().step+1;
    
46.                 p.s1=k;
    
47.                 p.s1.replace(as,s[i][0].size(),s[i][1]);
    
48.                 q.push(p);
    
49.                 as=k.find(s[i][0],j+1);
    
50.             }
    
51.         }
    
52.         q.pop();
    
53.     }
    
54.     cout<<"NO ANSWER!"<<endl;
    
55.     return 0;
    
56. }
    

复制代码

---

作者: universehyf    时间: 2018-10-25 21:23

1. #include<iostream>
   
2. #include<string>
   
3. #include<cstdio>
   
4. #include<queue>
   
5. #include<map>
   
6. using namespace std;
   
7. #define FOR(i,a,b) for(int i=a;i<=b;i++)
   
8. string a,b,x[15],y[15];
   
9. int c=1,ans,ttq;
   
10. struct node{string str;int step;};
    
11. map<string,int>mp;
    
12. string hyf(const string &str,int i,int j)
    
13. {
    
14.     string ans1="";
    
15.     if(i+x[j].size() > str.size() ) return ans1;
    
16.     FOR(k,0,x[j].size()-1)
    
17.         if(str[i+k]!=x[j][k])
    
18.             return ans1;
    
19.     ans1=str.substr(0,i);
    
20.     ans1+=y[j];
    
21.     ans1+=str.substr(i+x[j].size());
    
22. }
    
23. /*string hyf(const string &str,int i,int j){//借鉴了stdcall大爷的思想
    
24.     string ans = "";
    
25.     if (i+x[j].length() > str.length())
    
26.         return ans;
    
27. 
    
28.     for (int k=0; k < x[j].length();k++)
    
29.         if (str[i+k] != x[j][k])
    
30.             return ans;
    
31. 
    
32.     ans = str.substr(0,i);
    
33.     ans+=y[j];
    
34.     ans+=str.substr(i+x[j].length());
    
35.     return ans;
    
36. }*/
    
37. void bfs()
    
38. {
    
39.     queue <node> q;
    
40.     node tt;
    
41.     tt.str=a;
    
42.     tt.step=0;
    
43.     q.push(tt);
    
44.     while(!q.empty())
    
45.     {
    
46.         node u=q.front();
    
47.         q.pop();
    
48.         if(mp.count(u.str)==1) continue;
    
49.         if(u.str==b) {ans=u.step;break;}
    
50.         string temp;
    
51.         mp[u.str]=1;
    
52.         FOR(j,1,c)
    
53.         {
    
54.             ///ttq=u.str.size()-x[j].size()-1;ttq=max(ttq,0);
    
55.             FOR(i,0,u.str.size()-1)
    
56.             {
    
57.                 ///cout<<u.str.size()<<" "<<x[j].size()<<' '<<ttq<<endl;
    
58.                 temp=hyf(u.str,i,j);
    
59.                 if(temp!="")
    
60.                 {
    
61.                     ///cout<<temp<<endl;
    
62.                     node v;
    
63.                     v.str=temp;
    
64.                     v.step=u.step+1;
    
65.                     q.push(v);
    
66.                 }
    
67.             }
    
68.         }
    
69. 
    
70.     }
    
71.     if(ans>10 || ans==0)
    
72.         cout << "NO ANSWER!" << endl;
    
73.     else
    
74.         cout<<ans;
    
75. }
    
76. int main()
    
77. {
    
78.     cin>>a>>b;
    
79.     while(cin >> x[c] >> y[c]) c++;c--;
    
80.     bfs();
    
81.     return 0;
    
82. }

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2