题目描述
已知有两个字串A,BA,B及一组字串变换的规则（至多66个规则）:
A_1A1 ->B_1B1
A_2A2 -> B_2B2
规则的含义为：在 AA中的子串 A_1A1 可以变换为B_1B1，A_2A2 可以变换为 B_2B2 …。
例如：AA='abcdabcd'BB＝'xyzxyz'
变换规则为：
‘abcabc’->‘xuxu’‘udud’->‘yy’‘yy’->‘yzyz’
则此时，AA可以经过一系列的变换变为BB，其变换的过程为：
‘abcdabcd’->‘xudxud’->‘xyxy’->‘xyzxyz’
共进行了33次变换，使得AA变换为BB。
输入输出格式
输入格式：
输入格式如下：
AA BB
A_1A1 B_1B1
A_2A2 B_2B2 |-> 变换规则
... ... /
所有字符串长度的上限为2020。
输出格式：
输出至屏幕。格式如下：
若在1010步（包含1010步）以内能将AA变换为BB，则输出最少的变换步数；否则输出"NO ANSWER!"
输入输出样例
输入样例#1： 复制
abcd xyz
abc xu
ud y
y yz
输出样例#1： 复制
3 string.find（"string",pos) 从pos开始搜索string 先是用map迭代器来遍历
#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 1005
string s,ans;
map<string,string>mp;
struct node
{
string str;
int d;
}; void bfs()
{
node u,v;
u.str=s;
u.d=;
queue<node>q;
q.push(u);
while(!q.empty())
{
u=q.front();q.pop();
if(u.str==ans){printf("%d\n",u.d);return ;}
if(u.d>=){printf("NO ANSWER!\n");return ;}
map<string,string>::iterator it;
for(it=mp.begin();it!=mp.end();it++)
{
v=u;
v.d++;
int pos=;
while((pos=v.str.find(it->first,pos))!=v.str.npos )
{
pos+=;
node w=v;
w.str=v.str.substr(,pos-)+it->second+v.str.substr(pos+(it->first.size())-, v.str.size() );
q.push(w);
}
}
}
} int main()
{
cin>>s>>ans;
string a,b;
while(cin>>a>>b)
if(!mp.count(a))mp[a]=b;
bfs();
}
五个点一个WA 一个MLE
先不论那个MLE的 下载了WA的数据
abcdefgh
abcd efgh
efgh
efgh
数据
着实恶心。。
map只能一对一
这题不用map就能过 还方便了不少 不用迭代器
蒟蒻被自己蠢死了 用了一个麻烦还错的方法QAQ
bfs 最下面要写noanser 不然没到十次就结束了bfs岂不是什么都不输出（下载了数据才知道）
还有就是
while(cin>>fi[n]>>se[n])n++;
我一开始写成
while(cin>>fi[n]>>se[n++]);
是错的 虽然我还不知道为啥不行
还有。。注意这个map的用法
这个map真的剪枝了很多 之前那个map属实笨比
sub 好多细节 多看！
#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
#define N 1005
string s,ans;
string fi[N];
string se[N];
int n;
struct node
{
string str;
int d;
};
map<string,int>mp; string judge(string str,int i,int j)
{
if(i+fi[j].size()>str.size())return "";
int len=fi[j].size();
if(str.substr(i,len)==fi[j])
return str.substr(,i)+se[j]+str.substr(i+len,str.size()); return "";
} void bfs()
{
queue<node>q;
node u,v;
u.str=s;
u.d=;
q.push(u);
while(!q.empty())
{
u=q.front();q.pop();
if(u.str==ans){printf("%d\n",u.d);return;}
if(u.d>=){printf("NO ANSWER!\n");return;}
if(mp[u.str])continue;
mp[u.str]=;
u.d+=;
rep(i,,u.str.size()-)
rep(j,,n-)
{
string temp=judge(u.str,i,j);
if(temp!="")
{
v=u;
v.str=temp;
q.push(v);
}
}
}
printf("NO ANSWER!\n");
} int main()
{
cin>>s>>ans;
n=;
while(cin>>fi[n]>>se[n])n++;
bfs();
}