成都创新互联网站制作重庆分公司

BFS之单词最少转换次数

#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<

当前标题：BFS之单词最少转换次数
标题URL：http://cxhlcq.com/article/ggchjp.html

其他资讯

全国免费咨询:

400-028-6601

业务咨询：028-86922220 / 13518219792

节假值班：18980820575 / 13518219792

联系地址：成都市太升南路288号锦天国际A幢1002号

Copyright © 成都创新互联科技有限公司重庆分公司 渝ICP备2021005571号
友情链接:： 成都网站建设 重庆网站建设 四川网站建设 重庆建设网站 移动服务器托管 成都服务器托管 云服务器 广告设计制作 重庆网页设计 重庆做网站 重庆网站制作 重庆网站建设 重庆网站公司 渝中网站制作 重庆网站设计

在线咨询

微信咨询

电话咨询

028-86922220（工作日）

18980820575（7×24）

提交需求

返回顶部