洛谷题目链接:字串变换
题目描述
已知有两个字串 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
简述一下题意: 给出一个起始串,一个目标串,以及一堆变换方法.要求出能否在10步以内将起始串转换为目标串.
显然是直接广搜或者深搜.主要麻烦的就是处理这个字符串的变换.
为了方便起见,这里使用了STL自带的string类型.这里借鉴 copy 了一下洛谷的题解,学习了一下string类函数的用法.
下面主要讲一下string类函数吧.
-
定义一个string类型
-
对一个string类型进行赋值(下标以0为起点).
-
在一个string类型后加入一段字符.
-
length()返回一个string类型的长度.
-
begin()/end()返回一个迭代器,指向字符串的第一个/最后一个元素.
-
find()查找一个string类型内第一次出现某个字符串的下标.
-
erase()删除一个string类型中的一个子串(两个参数为下标和删除长度).
-
substr()查找一个string类型的字串.
string s; s = "this_is_string";//对string类型赋值 int len = s.length();//返回string类型的长度 printf("len=%d ",len); s += "_haha";//在string类型最后加上一个字符串 string::iterator it; string::iterator start = s.begin(); string::iterator end = s.end();//定义一个string类型的迭代器 for(it = start;it != end;it++) printf("%c",*it); printf(" "); int pos = s.find("is");//查找string类型中一个字符串第一个字母第一次出现的位置 cout << pos << endl; s.erase(s.find("_"),3); //s.erase(start+8,end-5);//同样也是删除 cout << s.substr() << endl;//默认直接输出整个string cout << s.substr(5) << endl;//从第5位截取到最后 cout << s.substr(5,6) << endl;//从第12位开始截取4的长度的字串
其实我觉得这道题并不是很难,但是这个转换字符的操作比较麻烦,所以主要就是写好这个转换字符的函数就好了.
#include<bits/stdc++.h>
using namespace std;
int cnt = 0;
string st, ed;
string c1[10], c2[10];
int step[100000];
string q[100000];
map <string,bool> vis;
string change(string s,int i,int j){
string ans = "";
if (i+c1[j].length() > s.length())
return ans;
for (int k=0; k < c1[j].length();k++)
if (s[i+k] != c1[j][k])
return ans;
ans = s.substr(0,i);
ans += c2[j];
ans += s.substr(i+c1[j].length());
return ans;
}
void bfs(){
int head = 1, tail = 1, len, x , flag = 0;
string now, nx;
q[tail] = st; vis[st] = 1;
while(head <= tail){
x = head; head++;
now = q[x]; len = now.length();
if(now == ed){flag = 1; break;}
for(int i=0;i<len;i++)
for(int j=1;j<=cnt;j++){//枚举每一位进行修改
nx = change(now,i,j);
if(vis[nx]) continue;
q[++tail] = nx; step[tail] = step[x]+1;
vis[nx] = 1;
}
}
if(flag && step[x] <= 10) printf("%d
",step[x]);
else printf("NO ANSWER!
");
}
int main(){
//freopen("data.in","r",stdin);
cin >> st >> ed;
while(cin >> c1[++cnt]) cin >> c2[cnt];
cnt--;
bfs();
return 0;
}