已知有两个字串 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 xyzabc xuud yy yz输出样例#1：3
第一反应是string，然而蒟蒻学艺不精，啥都不会string 这个博客很不错。
string后就没什么啦，第四个点注意一下，要剪掉一部分
替换后增加的最短长度*剩余最多步数如果还大于目标长度，剪掉替换后增加的最长长度*剩余最多步数如果还小于目标长度，剪掉贴代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 string ibeg,ifin; 4 map<string,int>h; 5 string a[10],b[10]; 6 int la[10],lb[10],mn=0x3f3f3f3f,mx=0,i=1; 7 void f(string x,int step) 8 { 9 if (step>=10) return ; 10 int u=x.size(),v=ifin.size(); 11 if (u+mx*(10-step)<v) return ; 12 if (u+mn*(10-step)>v) return ; 13 for (int j=1;j<i;j++) { 14 int pos=x.find(a[j],0); 15 while (pos != string::npos){ 16 string tmp=x; 17 tmp.replace(pos,la[j],b[j]); 18 if (( h[tmp]==0 && tmp!=ibeg) || (h[tmp]>h[x]+1) ) 19 { 20 h[tmp]=h[x]+1; 21 f(tmp,step+1); 22 } 23 pos=x.find(a[j],pos+1); 24 } 25 } 26 } 27 int main() 28 { 29 cin>>ibeg>>ifin; 30 while (cin>>a[i]>>b[i]) 31 { 32 la[i]=a[i].size(); 33 lb[i]=b[i].size(); 34 mn=min(mn,lb[i]-la[i]); 35 mx=max(mx,lb[i]-la[i]); 36 i++; 37 } 38 f(ibeg,0); 39 if ( h[ifin]!=0 ) printf("%d\n",h[ifin]); 40 else printf("NO ANSWER!"); 41 return 0; 42 }
代码 C++，1KB提交时间 2018-01-12 13:52:33耗时/内存 164ms, 4210KB
转载于:https://www.cnblogs.com/rtyz/p/8321366.html
