P1032 字串变换(replace函数)

2024-04-24 14:32

本文主要是介绍P1032 字串变换(replace函数),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

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

这道题明显看出就是bfs,唯一困难的一点就是在字符串的处理上……如何按照规则替换原有字符变成新的字符串并放到队列中,当然这些如果知道string的replace函数的话就不是问题……

replace(替换第i个字符开始,替换长度,替换旧字符串的新字符串)

顺便标记字符串是否用过可以用map

以下代码orz

#include <iostream>
#include <queue>
#include <map>
#include <string>
using namespace std;
//abcd xyz
//abc xu
//ud y
//y yz
string r[110],q[110];
map <string,int> flag;
struct st{string str;int step;st(string a,int b):str(a),step(b){}
};
int main()
{queue <st> qe;string a,b;cin>>a>>b;int i=0,j,k;while(cin>>r[i]>>q[i]) i++;int n=i;qe.push(st(a,0));while(!qe.empty()){st t=qe.front();qe.pop();if(t.step>10){cout<<"NO ANSWER!"<<endl;return 0;}if(b==t.str){cout<<t.step<<endl;return 0;}for(i=0;i<n;i++){for(j=0;j<t.str.length();j++){if(t.str[j]==r[i][0]){int g=j;int p=j;bool flag1=1;for(k=1,p=j+1;k<r[i].length()&&p<t.str.length();k++,p++){if(t.str[p]!=r[i][k]){flag1=0;break;}}if(flag1){string h=t.str;h.replace(g,r[i].length(),q[i]);if(!flag[h]){qe.push(st(h,t.step+1));//                  cout<<h<<endl;flag[h]=1;}}}}}}cout<<"NO ANSWER!"<<endl;return 0;}

这篇关于P1032 字串变换(replace函数)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/932020

相关文章

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

C++操作符重载实例(独立函数)

C++操作符重载实例,我们把坐标值CVector的加法进行重载,计算c3=c1+c2时,也就是计算x3=x1+x2,y3=y1+y2,今天我们以独立函数的方式重载操作符+(加号),以下是C++代码: c1802.cpp源代码: D:\YcjWork\CppTour>vim c1802.cpp #include <iostream>using namespace std;/*** 以独立函数

函数式编程思想

我们经常会用到各种各样的编程思想,例如面向过程、面向对象。不过笔者在该博客简单介绍一下函数式编程思想. 如果对函数式编程思想进行概括,就是f(x) = na(x) , y=uf(x)…至于其他的编程思想,可能是y=a(x)+b(x)+c(x)…,也有可能是y=f(x)=f(x)/a + f(x)/b+f(x)/c… 面向过程的指令式编程 面向过程,简单理解就是y=a(x)+b(x)+c(x)

利用matlab bar函数绘制较为复杂的柱状图,并在图中进行适当标注

示例代码和结果如下:小疑问:如何自动选择合适的坐标位置对柱状图的数值大小进行标注?😂 clear; close all;x = 1:3;aa=[28.6321521955954 26.2453660695847 21.69102348512086.93747104431360 6.25442246899816 3.342835958564245.51365061796319 4.87

OpenCV结构分析与形状描述符(11)椭圆拟合函数fitEllipse()的使用

操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C++11 算法描述 围绕一组2D点拟合一个椭圆。 该函数计算出一个椭圆,该椭圆在最小二乘意义上最好地拟合一组2D点。它返回一个内切椭圆的旋转矩形。使用了由[90]描述的第一个算法。开发者应该注意,由于数据点靠近包含的 Mat 元素的边界,返回的椭圆/旋转矩形数据

Unity3D 运动之Move函数和translate

CharacterController.Move 移动 function Move (motion : Vector3) : CollisionFlags Description描述 A more complex move function taking absolute movement deltas. 一个更加复杂的运动函数,每次都绝对运动。 Attempts to

Verybot之OpenCV应用二:霍夫变换查找圆

其实我是想通过这个程序来测试一下,OpenCV在Verybot上跑得怎么样,霍夫变换的原理就不多说了,下面是程序: #include "cv.h"#include "highgui.h"#include "stdio.h"int main(int argc, char** argv){cvNamedWindow("vedio",0);CvCapture* capture;i

✨机器学习笔记(二)—— 线性回归、代价函数、梯度下降

1️⃣线性回归(linear regression) f w , b ( x ) = w x + b f_{w,b}(x) = wx + b fw,b​(x)=wx+b 🎈A linear regression model predicting house prices: 如图是机器学习通过监督学习运用线性回归模型来预测房价的例子,当房屋大小为1250 f e e t 2 feet^

JavaSE(十三)——函数式编程(Lambda表达式、方法引用、Stream流)

函数式编程 函数式编程 是 Java 8 引入的一个重要特性,它允许开发者以函数作为一等公民(first-class citizens)的方式编程,即函数可以作为参数传递给其他函数,也可以作为返回值。 这极大地提高了代码的可读性、可维护性和复用性。函数式编程的核心概念包括高阶函数、Lambda 表达式、函数式接口、流(Streams)和 Optional 类等。 函数式编程的核心是Lambda

PHP APC缓存函数使用教程

APC,全称是Alternative PHP Cache,官方翻译叫”可选PHP缓存”。它为我们提供了缓存和优化PHP的中间代码的框架。 APC的缓存分两部分:系统缓存和用户数据缓存。(Linux APC扩展安装) 系统缓存 它是指APC把PHP文件源码的编译结果缓存起来,然后在每次调用时先对比时间标记。如果未过期,则使用缓存的中间代码运行。默认缓存 3600s(一小时)。但是这样仍会浪费大量C