搜索：广搜 词语阶梯
问题描述以及解决过程如下导图
广搜实现如下
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>using namespace std;/*判断两个单词是否有连接状态*/
bool connect(string &word1, string &word2) {if (word1.length() == 0 || word2.length() == 0) {return false;}int cnt = 0;for (int i = 0; i < word1.length(); ++i) {if (word1[i] != word2[i]) {cnt ++;}}if (cnt == 1) {return true;}return false;
}/*构建图*/
void get_graph(string &begin_word, std::vector<string> &wordList,std::map<string, std::vector<string> > &graph) {wordList.push_back(begin_word);for (int i = 0;i < wordList.size(); ++i ) {graph[wordList[i]]= std::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 get_length(string &begin_word, string &end_word,std::map<string, std::vector<string> > graph) {queue<pair<string,int>> Q;set<string> visit;Q.push(make_pair(begin_word,1));visit.insert(begin_word);while(!Q.empty()) {/* code */string node = Q.front().first;int step = Q.front().second;Q.pop();if (node == end_word) {return step;}std::vector<string> node_v = graph[node];for (int i = 0;i < node_v.size(); ++i) {if (visit.find(node_v[i]) == visit.end()) {Q.push(make_pair(node_v[i], step + 1));visit.insert(node_v[i]);}} }return 0;
}int get_result(string &begin_word, string &end_word, std::vector<string> &wordList) {std::map<string, std::vector<string> > graph;get_graph(begin_word,wordList,graph);return get_length(begin_word,end_word,graph);
}int main(int argc, char const *argv[])
{string begin_word = "hit";string end_word = "cog";std::vector<string> word_list;for (int i = 0;i < 6; ++i) {string tmp;cin >> tmp;word_list.push_back(tmp);}cout << get_result(begin_word, end_word, word_list);return 0;
}
输出如下:
#输入
hot
dot
dog
log
lot
cog#输出
5
相关文章：
float属性html,详解CSS样式中的float属性
详解CSS样式中的float属性。float是 css样式的定位属性。我们在印刷排版中，文本可以按照需要围绕图片。一般把这种方式称为“文本环绕”。在网页设计中，应用了CSS的float属性的页面元素就像在印刷布局里面的被文字包围的图片一样。浮动的元素仍然是网页流…
机房收费系统系列一：运行时错误‘-2147217843（80040e4d）’;用户‘sa’登陆失败...
做机房收费系统的时候，首先在SQL server数据库中添加好charge数据库（在对象资源管理器中，右击数据库，点击附加，找到charge的mdf文件，点击确定），然后用ODBC配置好数据库，把…
JQuery新浪1630个表情插件
1.http://***/Detail.aspx?id131 2.http://***/Detail.aspx?id81转载于:https://www.cnblogs.com/zrp2013/archive/2013/05/17/3082961.html
linux open系统调用的O_DIRECT标记
前言 open系统调用中针对打开的文件描述符，可以增加一个O_DIRECT标记，该标记能够使得针对该文件描述符的写操作绕过操作系统page cache，直接进入通用块设备层，从而减少页缓存对IO效率的影响。 但是针对O_DIRECT标记有一个问题&a…
计算机专业每年都有国企招老吗,这十大专业在国企中最受欢迎，待遇高、前景好，有你的专业吗？...
古语说“三百六十行，行行出状元”这句话一点没错，但是当你报考传说中的“铁饭碗”、“金饭碗”的时候，你会发现，想入对行，首先你得选对专业，不管是对于报考还是以后的职业发展来说，选对专业和嫁…
实现一个基于 SharePoint 2013 的 Timecard 应用（下）
现在，基于 Timecard 数据来一点儿数据分析。 应用需求 对于 Timecard，分析下面 2 个方面： 对于单个项目，分析其中每个成员的工时占比，以此了解工作量分配，为组间人员调度提供参考。对于整个公司，…
新书来了！《ActionScript 3.0游戏设计基础（第2版）》
已经开始预售：猛戳这里！多谢支持！文后附件为译者序。转载于:https://blog.51cto.com/58script/1202944
springcloud-spring cloud config统一配置中心
统一配置中心 为什么需要统一配置中心? 统一配置中心顾名思义,就是将配置统一管理,配置统一管理的好处是在日后大规模集群部署服务应用时相同的服务配置一致,日后再修改配置只需要统一修改全部同步,不需要一个一个服务手动维护 统一配置中心的架构图: 服务者消费者集群&#x…
a-awk外部变量传入，内部变量传出，同时过滤空格及其他字符
变量传递 外部变量传入 lsblk|awk -v A$A -v B$B {print A,B}lsblk | awk {print A,B} A$A B$B 内部变量传出 eval $(lsblk|awk {print "A$1"})eval $(lsblk|awk printf("A%s\n",$1)) 同时过滤空格及其他字符 df -Th|grep ceph- 2>/dev/null|awk -F…
UVa12096.The SetStack Computer
题目链接：http://uva.onlinejudge.org/index.php?optioncom_onlinejudge&Itemid8&pageshow_problem&problem3248 1391605812096The SetStack ComputerAcceptedC0.3022014-07-21 03:43:15The SetStack Computer Background from Wikipedia: \Set theory…
网络设置计算机,怎么重置电脑网络设置
现如今网络已经融入了我们的生活，我们对网络的要求也越来越过了，那么你知道怎么重置电脑网络设置吗?下面是学习啦小编整理的一些关于怎么重置电脑网络设置的相关资料，供你参考。重置电脑网络设置的方法开始→运行→输入：CMD 点击…
centos 学习日记 文件默认权限：umaks
使用方法： [rootkin /]# umask 0022 [rootkin /]# umask -S urwx,grx,orx上面显示的是本机上面文件默认的权限。 第二个好理解。 第一个要注意的是： umask的分值是指"该默认值需要减掉的权限" 第一个数字可以不管他 第二，三&…
linux 基础命令一
linux命令基础 hash：hash操做 shell搜寻到的外部命令的路径结果会缓存至kv(key-value)存储中history：查看历史 history命令:管理命令历史。登录shell时,会读取命令历史文件中记录下的命令:~/.bash_history，而且新执行的命令只会记录在缓存中:…
ceph pool 相关命令
文章目录Pool创建ec pool创建副本pool创建Pool参数创建根故障域及添加osd其他命令Tier相关Pool创建 ec pool创建 创建profile ceph osd erasure-code-profile set $profile_name k$k m$m crush-failure-domainhost crush-root$group_name 创建规则 ceph osd crush rule creat…
临平职高计算机专业高职考大学,临平职高高考再传捷报 本科连续四年蝉联杭州市第一...
又到一年放榜时，几家欢喜几家愁。然而，2018年的高考成绩出来后，可把临平市职业高级中学(以下简称“临平职高”)的师生们乐坏了。正所谓三年寒窗，开出芬芳；三年磨剑，努力未变；三年坚守࿰…
音频编辑大师 3.3 注冊名 注冊码
username：cae3_user000注冊码：beslbFVpFEhxvxA0F23xW7heAeWoWjuWhvBIMN0Je1o我试过了，绝对能够用。转载于:https://www.cnblogs.com/mfrbuaa/p/3858221.html
兰戈 —— Rango
2019独角兽企业重金招聘Python工程师标准>>> 一部西部卡通片，据说恶搞了《正午》这部著名的西部片，可惜我没有看过《正午》。非常喜欢这部片子里的音乐，恢宏大气。 剧情： 兰戈（约翰尼德普 Johnny Depp 配…
C#/.Net判断是否为周末/节假日
判断节假日请求的Api：http://tool.bitefu.net/jiari/ /// <summary>/// 判断是不是周末/节假日/// </summary>/// <param name"date">日期</param>/// <returns>周末和节假日返回true，工作日返回false</retu…
ceph 部署单机集群
文章目录ceph-deploy部署集群ceph-deploy 部署单机ceph-deploy 创建osdceph osd创建资源池ceph创建rbd块设备ceph创建fs文件系统本文档主要参考ceph官方命令进行部署，使用的时侯ceph-deploy原生命令方式进行集群各个组件的创建，删除，后续会增…
hdu-4302-Holedox Eating-线段树-单点更新，有策略的单点查询
一開始实在是不知道怎么做，后来经过指导，猛然发现，仅仅须要记录某个区间内是否有值就可以。 flag[i]:代表i区间内，共同拥有的蛋糕数量。 放置蛋糕的时候非常好操作，单点更新。 ip：老鼠当前的位置 寻找吃哪一…
华南理工计算机基础知识题,华南理工_计算机应用基础_随堂练习答案(2017年)
华南理工_计算机应用基础_随堂练习答案(2017年) (18页)本资源提供全文预览，点击全文预览即可全文预览,如果喜欢文档就下载吧，查找使用更方便哦！19.9 积分. . . .华南理工-计算机应用基础-随堂练习答案(2017年)第一章 计算机基础知…
python 添加进度条
安装： pip install tqdm使用： from tqdm import tqdm import time for i in tqdm(rang(10)):time.sleep(0.1)转载于:https://www.cnblogs.com/royfans/p/10271496.html
ceph osd 相关命令
混合osd的部署 先部署所有的ssd 在/etc/ceph.conf中最后添加ssd做osd的block大小如下： 比如部署中有两个ssd，则添加 [osd.0] bluestore_block_size xxxx [osd.1] bluestore_block_size xxx 如上的size大小计算如下，如ssd容量为800G&#x…
一万年太久，只争朝夕
好久没有写了，很多东西都已经忘记，不是因为别的，仅仅是觉得经历太多，没有地方装载那么多，想想以前的愿望，想过要当作家、想过要开个小店，但是看看现在，一切都变得遥不可及࿰…
上海职称英语和计算机考试时间,上海职称英语考试时间
上海2015年职称英语考试时间为12月25日到2015年1月15日，报名网站为：上海职业能力考试院。2015年如何短时间攻破职称英语考试关键点一：调整好备考心态，树立信心，切记懂乱、随便放弃总的来说，职称英语考生以中…
Caliburn.Micro 资源随时添加
Caliburn.Micro – Hello World http://buksbaum.us/2010/08/01/caliburn-micro-hello-world/ http://blog.csdn.net/xbgzs2010/article/details/18447625 转载于:https://www.cnblogs.com/ifendou/p/3870256.html
ros-kinetic install error: sudo rosdep init ImportError: No module named 'rosdep2'
refer to: https://blog.csdn.net/yueyueniaolzp/article/details/85070093 方法一 将Ubuntu默认python版本设置为2.7方法二 终端输入命令sudo apt-get install python3-rosdep转载于:https://www.cnblogs.com/xbit/p/10275218.html
Android：项目关联Library
为什么80%的码农都做不了架构师？>>> 近日，在做一个人人的第三方小项目。打算直接使用renren 的sdk 进行开发。因为renren的sdk是以android library project 形式发布的（关于这种project的内容可以参考android library project&…
winxp运行html代码,关于WinXP系统实现自动化运行的操作技巧
关于WinXP系统实现自动化运行的操作技巧发布时间：2014-06-16 10:00:29 作者：佚名 我要评论与其他系统相比，WinXP系统的自动化运行已经大大改进，根据经验为大家总结了一份关于实现自动化运行的操作技巧，希望对大家…