代码随想录Day53图论4.md

字符串迁移

问题描述

给定一个strlist，求出在strlist中把beginSTR每次次改变一个字符转换为endSTR的最短路径，若不能完成此操作，返回0.

思路

首先beginSTR要怎么变才能到达endStr;
1.beginStr每次改变一个，改变的这个一定要在endStr中；
其次要实现最快的一条路径。
解法中：
通过visitMap记录已经走过的路；
为什么需要一个队列？
队列是实现广度优先搜索的关键，通过在队列中放入一次变换后的单词，然后对变换后的单词再进行一次字符替换，其中存放的未处理的字符串，进而实现层级的搜索。

实现

#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>
#include<unordered_map>
#include<queue>
using namespace std;
int main(){string beginStr,endStr,str;int n;cin>>n;unordered_set<string>strSet;cin>>beginStr>>endStr;strSet.insert(str);for(int i=0;i<n;i++){cin>>str;strSet.insert(str);}unordered_map<string,int> visitMap;queue<string> que;que.push(beginStr);visitMap.insert(pair<string,int>(beginStr,1));while(!que.empty()){string word = que.front();que.pop();int path = visitMap[word];for(int i=0;i<word.size();i++){string newword =word;for(int j=0;j<26;j++){newword[i]=j+'a';if(newword==endStr){cout<<path+1<<endl;return 0;}if(strSet.find(newword)!=strSet.end()&&visitMap.find(newword)==visitMap.end()){visitMap.insert(pair<string,int>(newword,path+1));que.push(newword);}}} }cout << 0 << endl;
}

有向图的完全可达性

dfs解法：
https://kamacoder.com/problempage.php?pid=1177

岛屿的周长

https://kamacoder.com/problempage.php?pid=1178