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


以前做过这道题,
但是是打表才过的最后一个点。
今天重做了一遍。
才悟到一个真理:
永远不要对STL产生过度依赖!
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<map>
 7 using namespace std;
 8 string bg,ed;
 9 struct guize
10 {
11     string a,b;
12 }gz[1001];
13 struct node
14 {
15     string zfc;
16     int step;
17 }now,nxt;
18 int num=1;
19 map<string,bool>mp;
20 int tot=0;
21 void bfs()
22 {
23     queue<node>q;
24     now.zfc=bg;now.step=0;
25     q.push(now);
26     while(q.size()!=0)
27     {
28         node p=q.front();
29         //cout<<p.zfc<<"*4654654"<<endl;
30         if(p.zfc==ed)
31         {
32             printf("%d",p.step);
33             exit(0);
34         }
35         if(p.step>10)
36         {
37             printf("NO ANSWER!");
38             exit(0);
39         }
40         q.pop();
41         mp[p.zfc]=1;
42         for(int i=1;i<=num-1;i++)
43         {
44             string tmp=p.zfc;
45             //int where=p.zfc.find(gz[i].a);
46             for(int j=0;j<p.zfc.length();j++)
47             {
48                 if(p.zfc[j]==gz[i].a[0])
49                 {
50                     int flag=0;
51                     for(int k=0;k<gz[i].a.length();k++)
52                     {
53                         tot++;
54                         if(tot>=4384380)
55                         {
56                             printf("NO ANSWER!");
57                             exit(0);
58                         }
59                         if(p.zfc[j+k]!=gz[i].a[k])
60                         {
61                             flag=1;break;
62                         }
63                         
64                         
65                     }
66                     if(flag==0)
67                     {
68                         int where=j;
69                         nxt.zfc=p.zfc.replace(where,gz[i].a.length(),gz[i].b);
70                         p.zfc=tmp;
71                         if(mp[nxt.zfc]==0)
72                         {
73                             
74                             mp[nxt.zfc]=1;
75                             nxt.step=p.step+1;
76                             //cout<<p.zfc<<"****"<<nxt.zfc<<"***"<<nxt.step<<endl;
77                             q.push(nxt);
78                         }
79                     }
80                 }
81             }
82         }
83     }
84 }
85 int main()
86 {
87     freopen("string.in","r",stdin);
88     freopen("string.out","w",stdout);
89     cin>>bg>>ed;
90     while(cin>>gz[num].a>>gz[num].b)
91     num++;
92     //for(int i=1;i<=num-1;i++)
93     //    cout<<gz[i].a<<"+++"<<gz[i].b<<endl;
94     bfs();
95     printf("NO ANSWER!");
96     return 0;
97 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Petrichor的专栏

Selective Search (选择搜索)

[1] Selective Search for Object Recognition [2] Computer vision seminar, 5/2/2...

97220
来自专栏Deep Learning 笔记

CNN+MNIST+INPUT_DATA数字识别

TALK IS CHEAP,SHOW ME THE CODE,先从MNIST数据集下载脚本Input_data开始

45130
来自专栏xingoo, 一个梦想做发明家的程序员

MSRA-TD5000数据集使用详解

详情参考MSRA的官方地址:http://www.iapr-tc11.org/mediawiki/index.php/MSRA_Text_Detection_5...

36530
来自专栏奇点大数据

再免费多看一章--k-means++

在k-means算法里开始选取的聚类中点是随机的,每次都会照成不同的聚类结果。有一个解决方案叫做k-means++,可以有效的选择初始聚类中心点。参考 http...

30270
来自专栏人工智能LeadAI

深度学习框架之一:Theano | Lasagne简单教程

参考Lasagne官网(http://lasagne.readthedocs.io/en/latest/)tutorial进行总结而来。 01 简介 Lasag...

53450
来自专栏锦小年的博客

MNIST数据集的格式转换

以前直接用的是sklearn或者TensorFlow提供的mnist数据集,已经转换为矩阵形式的数据格式。但是sklearn体用的数据集合并不全,一共只有300...

49750
来自专栏简书专栏

基于tensorflow的MNIST数据集手写数字分类预测

MNIST是Mixed National Institue of Standards and Technology database的简称,中文叫做美国国家标准...

21030
来自专栏IT派

【深度学习入门系列】TensorFlow训练线性回归

作者:董超 来源:腾讯云技术社区「腾云阁」 上一篇文章我们介绍了 MxNet 的安装,但 MxNet 有个缺点,那就是文档不太全,用起来可能是要看源代码才能理...

33930
来自专栏FD的专栏

10种深度学习算法的TensorFlow实现

这个 repository 是使用 TensorFlow 库实现的多种深度学习算法的实现。这个软件包的目标是作为一种命令行实用程序——你可以将其用来快速训练和评...

18440
来自专栏人工智能

深度学习框架之一:Theano

正文共7163个字,1张图,预计阅读时间18分钟。 参考Lasagne官网(http://lasagne.readthedocs.io/en/latest/)t...

21360

扫码关注云+社区

领取腾讯云代金券