65. [NOIP2002] 字串变换
★★ 输入文件：
string.in输出文件：string.out简单对比
时间限制：1 s 内存限制：128 MB[问题描述]
已知有两个字串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!"
[输入样例]
abcd xyz
abc xu
ud y
y yz[输出样例]
3
依然是大力暴搜...
单向 $BFS$ 的话开一个队列, 先把原串怼进去, 然后每次取队首字符串并尝试应用变换规则. 每应用成功一个变换后将变换后的字符串再怼回队列里. 一直重复直至变换得到待求串或者队列为空. 如果队列为空则说明不存在解. 用 $STL$ 里的 $std::string,std::pair,std::map$ 食用即可.
双向 $BFS$ 的话就从两端对称搜索, 但是深度限制在 $10$ 以内可能并不会显得多快OwO...
附双向 $BFS$ 的参考实现:
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> typedef std::pair<std::string,int> pr; int n;
int m;
int ans;
std::string from,to;
std::queue<pr> q1,q2;
std::string transform[][];
std::map<std::string,int> m1,m2;
std::pair<std::string,int> p1,p2; bool Search();
void Initialize();
std::string Replace(std::string,int,int,std::string); int main(){
Initialize();
if(Search())
std::cout<<ans<<std::endl;
else
std::cout<<"NO ANSWER!"<<std::endl;
return ;
} bool Search(){
int len,lenp;
while((!q1.empty())&&(!q2.empty())){
p1=q1.front();
len=p1.first.size();
for(int i=;i<len;i++){
for(int j=;j<m;j++){
lenp=transform[j][].size();
if(i+lenp<=len&&p1.first.compare(i,lenp,transform[j][])==&&m1.count(Replace(p1.first,i,lenp,transform[j][]))==){
p2.first=Replace(p1.first,i,lenp,transform[j][]);
p2.second=q1.front().second+;
if(p2.second>)
return false;
m1[p2.first]=p2.second;
q1.push(p2);
if(m2.count(p2.first)){
ans=p2.second+m2[p2.first];
return true;
}
}
}
}
q1.pop();
p1=q2.front();
len=p1.first.size();
for(int i=;i<len;i++){
for(int j=;j<m;j++){
lenp=transform[j][].size();
if(i+lenp<=len&&p1.first.compare(i,lenp,transform[j][])==&&m2.count(Replace(p1.first,i,lenp,transform[j][]))==){
p2.first=Replace(p1.first,i,lenp,transform[j][]);
p2.second=q2.front().second+;
if(p2.second>)
return false;
m2[p2.first]=p2.second;
q2.push(p2);
if(m1.count(p2.first)){
ans=p2.second+m1[p2.first];
return true;
}
}
}
}
q2.pop();
}
return false;
} void Initialize(){
std::ios::sync_with_stdio(false);
std::cin.tie();
std::cin>>from>>to;
while(std::cin>>transform[m][]>>transform[m][])
m++;
m1[from]=;
m2[to]=;
q1.push(std::make_pair(from,));
q2.push(std::make_pair(to,));
} inline std::string Replace(std::string s, int pos,int len,std::string p){
return s.replace(pos,len,p);
}
Backup