字符串接龙
文字讲解：110. 字符串接龙 | 代码随想录
解题思路
本题只需要求出最短路径的长度就可以了（想到广搜），不用找出具体路径。
所以这道题要解决两个问题：
- 图中的线是如何连在一起的
- 起点和终点的最短路径长度
判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。
然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。
注意点：
- 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
- 使用set来检查字符串是否出现在字符串集合里更快一些
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
string beginStr;
string endStr;
cin >> n;
cin >> beginStr >> endStr;
string str;
//用set来存字符串，查找更快
unordered_set<string> strSet;
for(int i =0 ;i < n ; i++)
{
cin>> str;
strSet.insert(str);
}
//还需要记录一下是否遍历过，顺便记录结果
unordered_map<string,int> visitedStr;
//开始广搜
queue<string> que;
que.push(beginStr);
visitedStr.insert(pair<string,int>(beginStr,1));
while(!que.empty())
{
string word = que.front();
que.pop();
int path = visitedStr[word]; //路径
int m = word.size();
//开始挨个去替换字符
for(int i = 0 ; i< m ; 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.count(newWord) && visitedStr.find(newWord)==visitedStr.end())
{
visitedStr.insert(pair<string,int>(newWord,path+1));
que.push(newWord);
}
}
}
}
std::cout << 0 << std::endl;
}有向图的完全可达性
文字讲解：105.有向图的完全可达性 | 代码随想录
解题思路
本题是一个有向图搜索全路径的问题。 只能用深搜（DFS）或者广搜（BFS）来搜。
深搜三部曲
1.确定参数
我们本题需要三个，一个是图，一个是当前遍历的节点，此外还需要一个一维数组来记录我们是否访问过
2.终止条件
当节点访问过，我们就返回
3.单层处理逻辑，以及处理目前搜索节点出发的路径
我们这里本不需要回溯，我们只需要判断节点是否都被遍历过即可，并非找出所有可行路径
#include<bits/stdc++.h>
using namespace std;
void dfs(const vector<list<int>>&graph , int key , vector<bool>& visited)
{
if(visited[key])
{
return; //访问过了就return
}
visited[key] = true;
list<int> keys = graph[key];
for(int key : keys)
{
dfs(graph,key,visited);
}
}
int main()
{
int n,k;
cin>>n >> k;
vector<list<int>> graph(n+1); //节点从1开始
vector<bool> visited(n+1,false);
int s , t;
while(k--)
{
cin >> s >> t;
graph[s].push_back(t);
}
dfs(graph,1,visited);
for(int i = 1 ; i<=n ; i++)
{
if(visited[i] == false)
{
cout << -1 << endl;
return 0;
}
}
cout << 1 << endl;
}岛屿的周长
文字讲解：106. 岛屿的周长 | 代码随想录
本题容易惯性思维，使用dfs或者bfs，但其实用不上
计算出总的岛屿数量，总的变数为：岛屿数量 * 4
因为有一对相邻两个陆地，边的总数就要减2，如图红线部分，有两个陆地相邻，总边数就要减2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
cin >> n >> m;
vector<vector<int>> grid(n,vector<int>(m,0));
int island = 0;
int cover = 0;
for(int i =0 ; i< n; i++)
{
for(int j = 0 ;j< m; j++)
{
cin>> grid[i][j];
}
}
for(int i =0 ; i< n; i++)
{
for(int j = 0 ;j< m; j++)
{
if(grid[i][j]==1)
{
island +=1;
if(i-1>=0 && grid[i-1][j]==1) cover++;
if(j-1>=0 && grid[i][j-1]==1) cover++; //只统计上和左，避免重复计算
}
}
}
cout << island*4 - cover * 2 << endl;
}
