第十一章：图论part04 110.字符串接龙 105.有向图的完全可达性 106.岛屿的周长（补）

任务日期：7.29

题目一链接：110. 字符串接龙 (kamacoder.com)

思路：将本题寻找附近的字符串等效于寻找四周的陆地，即寻找周围与当前字符只有一位不同的字符串，然后加入到队列中并标记上，在此基础上要将字符串对应路径长度，最后输出长度即可

代码：

#include <bits/stdc++.h>
//思路：将本题寻找附近的字符串等效于寻找四周的陆地，在此基础上要将字符串对应路径长度，最后输出长度即可
using namespace std;
int main() {int n;cin>>n;string beginstr,endstr;cin>>beginstr>>endstr;//定义一个字典集合，方便直接查找unordered_set<string> strlist;for(int i = 0;i < n;i ++) {string str;cin>>str;strlist.insert(str);}//定义一个地图，记录以string为结尾的路径长度，以便查找到endstr后直接返回长度//哈希表的插入和定义要注意unordered_map<string,int> visitedstr;//初始化visitedstr:插入beginstr，并且设置路径长度为1visitedstr.insert(pair<string,int> (beginstr,1));//进行bfsstd::queue<string> que;que.push(beginstr);while(!que.empty()) {string cur = que.front();que.pop();int path = visitedstr[cur];//需要一个变量提前记录一下当前字符串的路径长度for(int i = 0;i < cur.size();i ++){//依次换cur字符串的各个位置string neword = cur;//如果换当前位置那么需要保证其他位置不动，所以要重新定义一个newordfor(int j = 0;j < 26;j ++) {//每个位置依次便利26个字母neword[i] = j + 'a';if(neword == endstr) {cout<<path + 1;//第26行的作用在此体现return 0;}//确定递归终止条件if(strlist.count(neword) && !visitedstr.count(neword)) {//strlist里面有当前字符串并且当前字符串没有被标记que.push(neword);//第28行作用在此体现visitedstr.insert(pair<string,int> (neword,path + 1));第26行的作用在此体现：标记当前字符串并且当前路径+1}}}}cout<<0;return 0;
}

难点：1.哈希表集合和map的创建。集合：unordered_set<string> strlist;                                                               map:unordered_map<string,int> visitedstr;

2.哈希表的插入操作：visitedstr.insert(pair<string,int> (beginstr,1));

3.哈希表map的含义：以string为结尾的路径长度int.

4.用bfs求最短路径，原因在于它是一圈一圈的遍历，当到达目标点时当前路径长一定是最短路径。

,5.在每次便利一个新的string时要用path记录当前路径长度，

---

---

---

题目二链接：

思路：

代码：

难点：

解释细节1：

---

---

---

题目三链接：

思路：

代码：

难点：

解释细节1：