java bfs实现单词最少转换次数
admin
2023-02-14 12:40:04
0次

                                                           

#include
#include
#include
#include
#include
#include
using namespace std;
bool connect(string &word1,string &word2)
{
    int cnt = 0;
    for(int i = 0; i < word1.length(); i++)
    if(word1[i] != word2[i])
    cnt++;
    return cnt == 1;
}
void construct_graph(string &beginword,vector &wordlist, map > &graph)
{
    wordlist.push_back(beginword);
    for(int i = 0; i < wordlist.size(); i++)
    graph[wordlist[i]] = vector();

    for(int i = 0; i < wordlist.size(); i++)
        for(int j = i+1; j < wordlist.size(); j++)
    {
        if(connect(wordlist[i],wordlist[j]))
        {
            graph[wordlist[i]].push_back(wordlist[j]);
            graph[wordlist[j]].push_back(wordlist[i]);
        }
     } 
}
int BFS_wordlist(string &beginword, string &endword, map > &graph)
{
    queue > q;
    set visit;
    q.push(make_pair(beginword,1));
    visit.insert(beginword);
    while(!q.empty())
    {
        string node = q.front().first;
        int step = q.front().second;
        q.pop();
        if(node == endword)
        {
            return step;
        }

        vector brothers = graph[node];
        for(int i = 0; i < brothers.size(); i++)
        {
            if(visit.find(brothers[i]) == visit.end())
            {
                q.push(make_pair(brothers[i], step+1));
                visit.insert(brothers[i]);
            }
        }
    }
    return 0;
}
int main()
{
    string beginword,endword;
    vector wordlist;
    map > graph;
    wordlist.push_back("hot");
    wordlist.push_back("dot");
    wordlist.push_back("dog");
    wordlist.push_back("lot");
    wordlist.push_back("log");
    wordlist.push_back("cog");
    cin>>beginword;
    cin>>endword;
    construct_graph(beginword,wordlist,graph);
    cout<

上一篇：huffman的压缩原理和压缩过程

下一篇：如何用二进制求子集？

相关内容

热门资讯

通派龙湖御潮云上：当极核地段遇... 在2026年的郑州楼市版图中，如果要寻找一个能够同时承载“主城确定性”与“产品革新力”的坐标，通派龙...
追光引路人—记国家级线上线下混... 人物名片：吴建丽，教授，黄河科技学院医学部教师。主持国家级线上线下混合式一流课程1门、河南省线上线下...
加总理表态：若谈判破裂，会对美... 据凤凰卫视报道，7月23日，加拿大总理卡尼与各省省长和地区领导人举行会议，商讨应对美国最新一轮关税威...
从北京望中东：和平，虽远在中国... ◆笔者参与的分论坛“维护中东和平：挑战与出路”正在进行中。今年7月举行的第十四届世界和平论坛上，中东...
巨大冲击！美国AI“闭源高价售... 日本计算机社会学专家塚越健司7月24日发表题为《中国AI“Kimi K3”引发巨大冲击——撼动美国A...
人民锐评：中国籍数学家首获全球... 历史性的突破！日前，第二十一届菲尔兹奖得主名单揭晓，北大2007级本科校友王虹、邓煜双双获奖，无数网...
深度专访｜网易智企段毓铮：不敢... 企业AI的商业化，难点在于让客户敢用、会用、用得有效果。在WAIC现场，搜狐AI邀请到网易智企副总经...
来论｜从“菲尔兹奖”，看见科技... 王虹、邓煜分别凭借在调和分析与几何测度论、偏微分方程与数学物理领域的突破性工作，共同荣获2026年菲...
当清洁机器人爬上窗户，能否开启... 过去十年，清洁机器人的故事，几乎都发生在地面上。 扫地、拖地、洗地，从随机碰撞到激光导航，从人工洗抹...
冰箱通电发烫压缩不启动不制冷什... 1、很有可能是因为冰箱的压缩机内高压输出缓冲管出现了断裂，造成高压管不排气，低压管不吸气的这种状况，...