acwing-190. 字串变换(双向bfs)

全栈程序员站长

发布于 2022-09-22 15:07:53

2290

文章被收录于专栏：全栈程序员必看全栈程序员必看

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

第一行是两个给定的字符串 A 和 B。

接下来若干行，每行描述一组字串变换的规则。

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

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

输入样例：
abcd xyz
abc xu
ud y
y yz
输出样例：
3

题解双向bfs

#include<bits/stdc++.h>
using namespace std;
const int N = 6;
string a[6],b[6];
int n = 0;
unordered_map<string,int>dist1,dist2;
int extend(queue<string>&q1,queue<string>&q2,string a[],string b[],unordered_map<string,int>&dist1,unordered_map<string,int>&dist2){ 
   
    string t = q1.front();
    q1.pop();
    for(int i = 0;i < t.size();i ++){ 
   
        for(int j = 0;j < n;j ++){ 
   
            int len = a[j].size();
            if(t.substr(i,len) == a[j]){ 
   
                string state = t.substr(0,i) + b[j] + t.substr(i + len);
                if(dist2.count(state))return dist1[t] + 1 + dist2[state];
                if(dist1.count(state))continue;
                dist1[state] = dist1[t] + 1;
                q1.push(state);
            }
        }
    }
    return 11;
}
int bfs(string start,string end){ 
   
    queue<string>q1,q2;
    dist1[start] = 0;
    dist2[end] = 0;
    q1.push(start);
    q2.push(end);
    while(q1.size() && q2.size()){ 
   
        int t;
        if(q1.size() < q2.size()){ 
   
            t = extend(q1,q2,a,b,dist1,dist2);
        }
        else{ 
   
            t = extend(q2,q1,b,a,dist2,dist1);
        }
        if(t <= 10)return t;
    }
    
    return 11;
}

int main(){ 
   
    string start,end;
    cin>>start>>end;
    while(cin>> a[n] >> b[n])n ++;
    
    int ans = bfs(start,end);
    if(ans <= 10)cout<<ans<<endl;
    else cout<<"NO ANSWER!"<<endl;
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168635.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https