1099 字串变换 2002年NOIP全国联赛提高组
2018-06-17 22:42:53来源:未知 阅读 ()
1099 字串变换
2002年NOIP全国联赛提高组
已知有两个字串 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
hehe
string判重+删除
map记录步数,,
但是不知道为啥最后一个点过不了?
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<cstdlib> 6 #include<map> 7 using namespace std; 8 string a,b; 9 struct node 10 { 11 string x; 12 string y; 13 }bc[9]; 14 int num=1; 15 int step=0; 16 map<string,int>bushu; 17 string pc;// 18 int vis[101]; 19 void bfs() 20 { 21 queue<string>q; 22 q.push(a); 23 bushu[q.front()]=0; 24 25 while(q.size()!=0) 26 { 27 int numm=q.size(); 28 string p=q.front(); 29 if(p==b) 30 { 31 printf("%d",bushu[p]); 32 exit(0); 33 } 34 pc=pc+" "+p+" "; 35 q.pop(); 36 for(int i=1;i<=num;i++) 37 { 38 string dd=p; 39 string change=p; 40 while(1) 41 { 42 int where=change.find(bc[i].x); 43 if(where!=-1&&vis[where]==0) 44 { 45 vis[where]=1; 46 change[where]='*'; 47 48 int l=bc[i].x.length(); 49 p.replace(where,l,bc[i].y); 50 51 if(p==b) 52 { 53 printf("%d",bushu[dd]+1); 54 exit(0); 55 } 56 57 if(pc.find(p)!=-1)continue;// 判重 58 pc=pc+" "+p+" "; 59 60 bushu[p]=bushu[dd]+1; 61 62 cout<<step<<" "<<bushu[p]<<" "<<p<<endl; 63 64 if(p==b) 65 { 66 printf("%d",bushu[p]); 67 exit(0); 68 } 69 else 70 {step++;q.push(p);} 71 if(bushu[p]>10) 72 {printf("NO ANSWER!");exit(0);} 73 p=dd; 74 } 75 else break; 76 } 77 78 } 79 } 80 } 81 int main() 82 { 83 cin>>a>>b; 84 while(cin>>bc[num].x>>bc[num].y){num++;} 85 bfs(); 86 printf("NO ANSWER!"); 87 return 0; 88 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:2843 拯救炜哥
下一篇:bzoj4712 -- 树链剖分
- Z 字形变换 2020-04-14
- 用C++实现:01字串打印 2020-03-15
- 矩阵乘法(六):几何变换 2019-09-08
- 题解 Luogu P1099 【树网的核】 2019-08-16
- BFS(二):数的变换 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash