1099 字串变换 2002年NOIP全国联赛提高组

1099 字串变换

2002年NOIP全国联赛提高组

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题解

题目描述 Description

已知有两个字串 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$。

输入描述 Input Description

输入格式如下:

   A$ B$    A1$ B1$ \    A2$ B2$  |-> 变换规则    ... ... /    所有字符串长度的上限为 20。

输出描述 Output Description

若在 10 步(包含 10步)以内能将 A$ 变换为 B$ ,则输出最少的变换步数;否则输出"NO ANSWER!"

样例输入 Sample Input

abcd xyz abc xu ud y y yz

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

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 }

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C/C++基础

Dijkstra算法求单源最短路径

在一个连通图中,从一个顶点到另一个顶点间可能存在多条路径,而每条路径的边数并不一定相同。如果是一个带权图,那么路径长度为路径上各边的权值的总和。两个顶点间路径长...

3421
来自专栏wym

python实现 opencv 学习笔记---模板匹配matchTemplate

这是打印出result的值,下面一张图是计算公式,通过公式也可以知道匹配程度在什么情况下最好

5135
来自专栏人工智能LeadAI

译文 | 与TensorFlow的第一次接触 第三章:聚类

前一章节中介绍的线性回归是一种监督学习算法,我们使用数据与输出值(标签)来建立模型拟合它们。但是我们并不总是有已经打标签的数据,却仍然想去分析它们。这种情况下,...

4466
来自专栏人工智能

Tensorflow下Char-RNN项目代码详解

前言 Char-RNN,字符级循环神经网络,出自于Andrej Karpathy写的The Unreasonable Effectiveness of Recu...

66310
来自专栏小樱的经验随笔

MATLAB命令大全+注释小结

一、常用对象操作:除了一般windows窗口的常用功能键外。 1、!dir 可以查看当前工作目录的文件。   !dir& 可以在dos状态下查看。 2、who ...

3454
来自专栏Java Web

最长公共子序列问题

问题描述: 求两个字符序列的公共最长子序列。 ---- 最长公共子串 在回到子序列问题之前,先来了解一下子串的问题。 例如,HISH和FISH两个字符序列的公...

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

cuda中的二分查找

  使用背景 通常,在做高性能计算时,我们需要随机的连接某些点。这些点都具有自己的度量值,显然,度量值越大的值随机到的概率就会越大。因此,采用加权值得方法: v...

1965
来自专栏计算机视觉与深度学习基础

Codeforces 472D

看官方题解提供的是最小生成树,怎么也想不明白,you can guess and prove it! 看了好几个人的代码,感觉实现思路全都不一样,不得不佩服cf...

21510
来自专栏专注研发

poj-3185-开关问题

牛一行20他们喝的水碗。碗可以那么(面向正确的为清凉水)或颠倒的(一个位置而没有水)。他们希望所有20个水碗那么,因此用宽鼻子翻碗。

1133
来自专栏潇涧技术专栏

Problem: Longest Common Subsequence

最长公共子序列(LCS)是典型的动态规划问题,如果不理解动态规划请移步先看这篇动态规划的总结,否则本文中的代码实现会不理解的哟!

601

扫码关注云+社区

领取腾讯云代金券