[NOIP2002]字串变换 T2 双向BFS

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目描述

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

输入

第一行为两个字符串，第二行至文件尾为变换规则

A1B1 \

A2B2 |-> 变换规则

... ... / 所有字符串长度的上限为 20。

输出

若在 10 步（包含 10步）以内能将 A变换为变换为B ，则输出最少的变换步数；否则输出"NO ANSWER!"

样例输入

abcd xyz abc xu ud y y yz

样例输出

(⊙o⊙)…

大概并不是很简单，我以为BFS就行...

但是.....

时间超限...

尴尬，GG

(⊙o⊙)…双向BFS弄完了就只剩下一点string的东西了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<map>
using namespace std;
const int N=;
struct Node
{
string s;
int d;
};
map<string,int> m1,m2;
queue<Node> q1,q2;
string change[N][],ss;
Node s1,s2;
int k,ans;
int dbfs()
{
while(!q1.empty()||!q2.empty())
{
if(q1.front().d+q2.front().d>) break;
s1=q1.front();
int len=s1.s.length();
for(int i=;i<len;i++)
{
for(int j=;j<k;j++)
{
int tmp=change[j][].length();
ss=s1.s;
if(i+tmp-<len&&!s1.s.compare(i,tmp,change[j][])&&!m1.count(ss.replace(i,tmp,change[j][])))
{
s2.s=ss;
s2.d=q1.front().d+;
m1[s2.s]=s2.d;
q1.push(s2);
if(m2.count(s2.s))
{
return s2.d+m2[s2.s];
}
}
}
}
q1.pop();
s1=q2.front();
len=s1.s.length();
for(int i=;i<len;i++)
{
for(int j=;j<k;j++)
{
int tmp=change[j][].length();
ss=s1.s;
if(i+tmp-<len&&!s1.s.compare(i,tmp,change[j][])&&!m2.count(ss.replace(i,tmp,change[j][])))
{
s2.s=ss;
s2.d=q2.front().d+;
m2[s2.s]=s2.d;
q2.push(s2);
if(m1.count(s2.s))
{
return s2.d+m1[s2.s];
}
}
}
}
q2.pop();
}
puts("NO ANSWER!");
exit();
return ;
}
int main()
{
cin>>s1.s>>s2.s;
if(s1.s==s2.s){cout<<<<endl;return ;}
s1.d=s2.d=;
q1.push(s1);q2.push(s2);
m1[s1.s]=;m2[s2.s]=;
while(cin>>change[k][]>>change[k][])k++;
cout<<dbfs()<<endl;
return ;
}

RE的，谁大概给我看看为什么...

#include<cstdio>
#include<iostream>
#include<map>
#include<string>
#include<queue>
using namespace std;
typedef struct{string s;int d;}point;
map<string,int> m1,m2;
queue<point> q1,q2;
string change[][],ss;
point s1,s2;
int k,ans;bool dbfs(){
while(!q1.empty()&&!q2.empty()){
if(q1.front().d+q2.front().d>)return false;
s1=q1.front();
int len=s1.s.length();
for(int i=;i<len;i++)
for(int j=;j<k;j++){
int tmp=change[j][].length();
ss=s1.s;
if(i+tmp-<len&&!s1.s.compare(i,tmp,change[j][])&&!m1.count(ss.replace(i,tmp,change[j][]))){
s2.s=ss;
s2.d=q1.front().d+;
m1[s2.s]=s2.d;
q1.push(s2);
if(m2.count(s2.s)){ans=s2.d+m2[s2.s];return true;}
}
}
q1.pop();
s1=q2.front();
len=s1.s.length();
for(int i=;i<len;i++)
for(int j=;j<k;j++){
int tmp=change[j][].length();
ss=s1.s;
if(i+tmp-<len&&!s1.s.compare(i,tmp,change[j][])&&!m2.count(ss.replace(i,tmp,change[j][]))){
s2.s=ss;
s2.d=q2.front().d+;
m2[s2.s]=s2.d;
q2.push(s2);
if(m1.count(s2.s)){ans=s2.d+m1[s2.s];return true;}
}
}
q2.pop();
}
return false;
}int main(){
cin>>s1.s>>s2.s;
if(s1.s==s2.s){cout<<<<endl;return ;}
s1.d=s2.d=;
q1.push(s1);q2.push(s2);
m1[s1.s]=;m2[s2.s]=;
while(cin>>change[k][]>>change[k][])k++;
if(dbfs())cout<<ans<<endl;
else printf("NO ANSWER!");
return ;
}