牛客：[NOIP2002]字串变换（双向bfs）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

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

abcd xyz
abc xu
ud y
y yz

输出

复制3

3

做法

#include<bits/stdc++.h>
using namespace std;
string s,t,a[10],b[10];
int n;
queue<string> q1,q2;
unordered_map<string,int> mp1,mp2;
int bfs(){
    int step=0;
    q1.push(s);
    q2.push(t);
    mp1[s]=0;
    mp2[t]=0;
    while(++step<=5){ 
        while(mp1[q1.front()]==step-1){//上一层的
            string tmp=q1.front();
            q1.pop();
            
            for(int i=0;i<n;i++){
            int pos=0;
            while(pos<tmp.size()){
                string ss=tmp;
                if(ss.find(a[i],pos)==-1) break;//子串没有包含a[i]
                ss.replace(ss.find(a[i],pos),a[i].size(),b[i]);//注意起始点
                if(mp1.find(ss)!=mp1.end()) {
                        pos++;
                        continue;//搜过了
                    }
                if(mp2.find(ss)!=mp2.end()) return step*2-1;//会合，当前这步不算
                q1.push(ss);
                mp1[ss]=step;
                pos++;
                }
            }
        }
        
        while(mp2[q2.front()]==step-1){
            string tmp=q2.front();
            q2.pop();
            
           for(int i=0;i<n;i++){
            int pos=0;
            while(pos<tmp.size()){
                string ss=tmp;
                if(ss.find(b[i],pos)==-1) break;
                ss.replace(ss.find(b[i],pos),b[i].size(),a[i]);
                if(mp2.find(ss)!=mp2.end()) {
                        pos++;
                        continue;//搜过了
                    }
                if(mp1.find(ss)!=mp1.end()) return step*2;
                mp2[ss]=step;
                q2.push(ss);
                pos++;
            }
            }
        }
    }
    return -1;
}
int main(){
cin>>s>>t;
while(cin>>a[n]>>b[n]) n++;
int ans=bfs();
if(ans==-1) cout<<"NO ANSWER!";
    else cout<<ans;
}

原文地址：https://blog.csdn.net/2301_80718054/article/details/142833810

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！