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)


相关推荐

  • javaScript模块化解析「建议收藏」

    javaScript模块化解析「建议收藏」JavaScript模块化解析什么是模块化?到底什么是模块化、模块化开发呢?事实上模块化开发最终的目的是将程序划分成一个个小的结构;这个结构中编写属于自己的逻辑代码,有自己的作用域,不会影响到其他的结构;这个结构可以将自己希望暴露的变量、函数、对象等导出给其结构使用;也可以通过某种方式,导入另外结构中的变量、函数、对象等;上面说提到的结构,就是模块;按照这种结构划分开发程序的过程,就是模块化开发的过程;无论你多么喜欢JavaScript,以及它现在发展的有多好,它都有很多的缺陷:比如

  • jvm的垃圾回收机制是什么_垃圾回收过程图片

    jvm的垃圾回收机制是什么_垃圾回收过程图片如果大家对java架构相关感兴趣,可以关注下面公众号,会持续更新java基础面试题,netty,springboot,springcloud等系列文章,一系列干货随时送达,超神之路从此展开,BTAJ不再是梦想!垃圾回收的过程分为两步:1.判断对象是否死亡(1)引用计数器法:①每当有一个对象引用是,计数器加一,当计数器为0是对象死亡②缺点:无法解决循环引用的问题,假设A引用B,B引用A,那么这两个对象将不会被回收,造成内存泄漏(2)可达性算法分析①通过一系列可作为GCRoot

  • 深度学习中学习率和batchsize对模型准确率的影响

    本内容来自其他的人解析,参考链接在最后的注释。1.前言目前深度学习模型多采用批量随机梯度下降算法进行优化,随机梯度下降算法的原理如下:n是批量大小(batchsize),η是学习率(learningrate)。可知道除了梯度本身,这两个因子直接决定了模型的权重更新,从优化本身来看它们是影响模型性能收敛最重要的参数。学习率直接影响模型的收敛状态,batchsize则影响模型的泛化性能,两者又是分子分母的直接关系,相互也可影响,因此这一次来详述它们对模型性能的影响。2.学习率如何影响模型性.

  • Redis雪崩_redis落地方式

    Redis雪崩_redis落地方式同一时间大面积失效,那一瞬间Redis跟没有一样,那这个数量级别的请求直接打到数据库几乎是灾难性的,如果打挂的是一个用户服务的库,那其他依赖他的库所有的接口几乎都会报错,如果没做熔断等策略基本上就是瞬间挂一片的节奏,怎么重启用户都会把你打挂,等你能重启的时候,用户早就睡觉去了,并且对产品失去了信心,什么垃圾产品。设置两个缓存,原始缓存和备用缓存,原始缓存失效时,访问备用缓存,备用缓存失效时间设置长点。设置缓存过期时间时加上一个随机值,避免缓存在同一时间过期。雪崩概念在某一个时间段,缓存集中过期失效。…

  • [安全攻防进阶篇] 二.如何学好逆向分析、逆向路线推荐及吕布传游戏逆向案例

    [安全攻防进阶篇] 二.如何学好逆向分析、逆向路线推荐及吕布传游戏逆向案例前文作者带领大家学习了什么是逆向分析、逆向分析的典型应用,接着通过OllyDbg工具逆向分析经典的游戏扫雷。这篇文章将继续普及逆向分析知识,告诉大家如何学好逆向分析,并结合作者经验给出逆向分析的路线推荐,最后给出吕布传游戏逆向案例。话不多说,让我们开始新的征程吧!您的点赞、评论、收藏将是对我最大的支持,感恩安全路上一路前行。基础性文章,希望对您有所帮助~

  • maven使用入门[通俗易懂]

    maven使用入门[通俗易懂]maven面临的问题一个项目就是一个工程。如果项目非常大,最好是每一个模块对应一个工程。借助maven可以将一个项目拆分成多个工程项目中需要的jar必须要手动”复制”,”粘贴”到WEB-INF/lib目录下,带来的问题是:同样的jar包文件重复出现在不同的项目工程中,浪费空间。maven可以将jar仅仅保存在”仓库”中,有需要使用的工程”引用”这个文件接口,并不需要真的把jar包复制过来jar包需要别人替我们准备好,或到官网下载。不同技术的官网提供jar包下载的形式是五花八门的,有些技术的官网就是

发表回复

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

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