中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

BFS之單詞最少轉換次數

發布時間:2020-08-06 15:14:12 來源:網絡 閱讀:114 作者:wx5d3c7e0ad6c30 欄目:編程語言
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<map>
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<string> &wordlist, map<string ,vector<string> > &graph)
{
    wordlist.push_back(beginword);
    for(int i = 0; i < wordlist.size(); i++)
    graph[wordlist[i]] = vector<string>();

    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<string, vector<string> > &graph)
{
    queue<pair<string,int> > q;
    set<string> 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<string> 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<string> wordlist;
    map<string ,vector<string> > 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_wordlist(beginword,endword,graph);
    return 0;
}
向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

陆川县| 滦平县| 英德市| 柏乡县| 共和县| 天峻县| 双柏县| 竹山县| 仁怀市| 乌拉特前旗| 南宫市| 清水县| 鄂托克前旗| 沙雅县| 辽宁省| 南江县| 泸西县| 山阳县| 石首市| 老河口市| 福建省| 建平县| 淳安县| 邢台县| 红河县| 个旧市| 康乐县| 芒康县| 会理县| 聂荣县| 临高县| 昔阳县| 丘北县| 古田县| 锡林浩特市| 将乐县| 彩票| 铜陵市| 剑川县| 东丰县| 保康县|