110.字符串接龙
110. 字符串接龙
题目描述
字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：
1. 序列中第一个字符串是 beginStr。
2. 序列中最后一个字符串是 endStr。
3. 每次转换只能改变一个字符。
4. 转换过程中的中间字符串必须是字典 strList 中的字符串，且strList里的每个字符串只用使用一次。
给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。
输入描述
第一行包含一个整数 N，表示字典 strList 中的字符串数量。 第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。 后续 N 行，每行一个字符串，代表 strList 中的字符串。
输出描述
输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。
输入示例
6 abc def efc dbc ebc dec dfc yhn输出示例
4提示信息
从 startStr 到 endStr，在 strList 中最短的路径为 abc -> dbc -> dec -> def，所以输出结果为 4，如图：
数据范围：
2 <= N <= 500
思路
可以看出 abc 到 def的路线 不止一条，但最短的一条路径上是4个节点。
求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。
- 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
- 使用set来检查字符串是否出现在字符串集合里更快一些
（y1s1，无视频的日子有点难受。。）
代码
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>// 是一个队列，用于BFS遍历过程中的节点管理。
using namespace std;
int main() {string beginStr, endStr, str;int n;cin >> n;unordered_set<string> strSet;cin >> beginStr >> endStr;for (int i = 0; i < n; i++) {cin >> str;strSet.insert(str);}// 记录strSet里的字符串是否被访问过，同时记录路径长度unordered_map<string, int> visitMap; // <记录的字符串，路径长度>// 初始化队列queue<string> que;que.push(beginStr);// 初始化visitMapvisitMap.insert(pair<string, int>(beginStr, 1));while(!que.empty()) {string word = que.front();que.pop();int path = visitMap[word]; // 这个字符串在路径中的长度//对于word的每一个字符，尝试用'a'到'z'之间的任意字符替换它，生成新的单词newWord。
//如果newWord等于endStr，则找到了一条从beginStr到endStr的路径，输出路径长度path + 1并结束程序。
//如果newWord存在于strSet中且未被访问过，则将newWord加入队列，并更新visitMap以记录其已被访问及路径长度。for (int i = 0; i < word.size(); i++) {string newWord = word; // 用一个新字符串替换str，因为每次要置换一个字符// 遍历26的字母for (int j = 0 ; j < 26; j++) {newWord[i] = j + 'a';if (newWord == endStr) { // 发现替换字母后，字符串与终点字符串相同cout << path + 1 << endl; // 找到了路径 return 0;}// 字符串集合里出现了newWord，并且newWord没有被访问过if (strSet.find(newWord) != strSet.end()&& visitMap.find(newWord) == visitMap.end()) {// 添加访问信息，并将新字符串放到队列中visitMap.insert(pair<string, int>(newWord, path + 1));que.push(newWord);}}}}// 没找到输出0cout << 0 << endl;}105.有向图的完全可达性
105. 有向图的完全可达性
题目描述
给定一个有向图，包含 N 个节点，节点编号分别为 1，2，...，N。现从 1 号节点开始，如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。
输入描述
第一行包含两个正整数，表示节点数量 N 和边的数量 K。 后续 K 行，每行两个正整数 s 和 t，表示从 s 节点有一条边单向连接到 t 节点。
输出描述
如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。
输入示例
4 4 1 2 2 1 1 3 2 4输出示例
1提示信息
从 1 号节点可以到达任意节点，输出 1。
数据范围：
1 <= N <= 100；
1 <= K <= 2000。
思路
有向图搜索全路径的问题。
深搜三部曲：
- 确认递归函数，参数
需要传入地图，需要知道当前我们拿到的key，以至于去下一个房间。
同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。
- 确认终止条件
在递归中，我们是处理当前访问的节点，还是处理下一个要访问的节点。
这决定 终止条件怎么写。
首先明确，本题中什么叫做处理，就是 visited数组来记录访问过的节点，该节点默认 数组里元素都是false，把元素标记为true就是处理 本节点了。
如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。
如果我们是处理下一层访问的节点，而不是当前层。那么就要在 深搜三部曲中第三步：处理目前搜索节点出发的路径的时候对 节点进行处理。
这样的话，就不需要终止条件，而是在 搜索下一个节点的时候，直接判断 下一个节点是否是我们要搜的节点。
代码
dfs写法一，处理当前节点，需要终止条件。
本题的递归没有回溯操作，因为要看是否能到达所有节点，所以只需要记录遍历过的节点就可以了。。
#include<iostream>
#include<vector>
#include<list>
using namespace std;
//使用邻接表
void dfs(const vector<list<int>>&graph,int key,vector<bool>&visited)
{//处理当前节点if(visited[key])return;//如果节点被访问过，则返回，不然就标记visited[key]=true;list<int>keys=graph[key];for(int key:keys){dfs(graph,key,visited);//深度优先搜索遍历}}int main()
{int n,m,s,t;cin>>n>>m;//n+1大的数组vector<list<int>>graph(n+1);while(m--)//边关系{cin>>s>>t;//使用邻接表，表示s->t是相连的graph[s].push_back(t);}vector<bool>visited(n+1,false);dfs(graph,1,visited);//深度搜索看看是否可达//检查是否都访问了for(int i=1;i<=n;i++){if(visited[i]==false){cout<<-1<<endl;return 0;//如果有一点未被访问过}}cout<<1<<endl;}106.岛屿的周长
106. 岛屿的周长
题目描述
给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。
你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算岛屿的周长。岛屿内部没有水域。
输入描述
第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。
输出描述
输出一个整数，表示岛屿的周长。
输入示例
5 5 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0输出示例
14提示信息
岛屿的周长为 14。
数据范围：
1 <= M, N <= 50。
思路
本题bfs和dfs都不需要
解法一
遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。
如果该陆地上下左右的空格是有水域，则说明是一条边，如图：
陆地的右边空格是水域，则说明找到一条边。
如果该陆地上下左右的空格出界了，则说明是一条边
解法二
计算出总的岛屿数量，总的变数为：岛屿数量 * 4
因为有一对相邻两个陆地，边的总数就要减2，如图红线部分，有两个陆地相邻，总边数就要减2
那么只需要在计算出相邻岛屿的数量就可以了，相邻岛屿数量为cover。
结果 result = 岛屿数量 * 4 - cover * 2;
代码
解法一
#include <iostream>
#include <vector>
using namespace std;
int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}int direction[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};int result = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) {for (int k = 0; k < 4; k++) { // 上下左右四个方向int x = i + direction[k][0];int y = j + direction[k][1]; // 计算周边坐标x,yif (x < 0 // x在边界上|| x >= grid.size() // x在边界上|| y < 0 // y在边界上|| y >= grid[0].size() // y在边界上|| grid[x][y] == 0) { // x,y位置是水域result++;}}}}}cout << result << endl;}解法二
#include <iostream>
#include <vector>
using namespace std;
int main() {int n, m;cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}int sum = 0; // 陆地数量int cover = 0; // 相邻数量for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) {sum++; // 统计总的陆地数量// 统计上边相邻陆地if(i - 1 >= 0 && grid[i - 1][j] == 1) cover++;// 统计左边相邻陆地if(j - 1 >= 0 && grid[i][j - 1] == 1) cover++;// 为什么没统计下边和右边？ 因为避免重复计算}}}cout << sum * 4 - cover * 2 << endl;}
![Ubuntu[无桌面]——修改Docker镜像源文件](https://i-blog.csdnimg.cn/direct/e462cfaa254748ea8e9a98a2e7e025e2.png)
