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

acwing-190. 字串变换(双向bfs)已知有两个字串 A, B 及一组字串变换的规则(至多 6 个规则):A1→B1A2→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 BA1 B1A2 B2… …第一行是两个给定的字符串

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

已知有两个字串 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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168635.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号