当前位置：首页 > news >正文

代码训练营DAY53 第十一章：图论part04

news 2025/8/6 7:20:08

110. 字符串接龙

题目描述

字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列：

序列中第一个字符串是 beginStr。
序列中最后一个字符串是 endStr。
每次转换只能改变一个位置的字符（例如 ftr 可以转化 fty ，但 ftr 不能转化 frx）。
转换过程中的中间字符串必须是字典 strList 中的字符串。
beginStr 和 endStr 不在字典 strList 中
字符串中只有小写的26个字母

给你两个字符串 beginStr 和 endStr 和一个字典 strList，找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列，返回 0。

输入描述

第一行包含一个整数 N，表示字典 strList 中的字符串数量。第二行包含两个字符串，用空格隔开，分别代表 beginStr 和 endStr。后续 N 行，每行一个字符串，代表 strList 中的字符串。

输出描述

输出一个整数，代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列，则输出 0。

输入示例

6
abc def
efc
dbc
ebc
dec
dfc
yhn

输出示例

提示信息

从 startStr 到 endStr，在 strList 中最短的路径为 abc -> dbc -> dec -> def，所以输出结果为 4

思路

以示例1为例，从这个图中可以看出 abc 到 def的路线不止一条，但最短的一条路径上是4个节点。

本题只需要求出最短路径的长度就可以了，不用找出具体路径。

所以这道题要解决两个问题：

1、图中的线是如何连在一起的

在搜索的过程中，我们可以枚举，用26个字母替换当前字符串的每一个字符，在看替换后是否在 strList里出现过，就可以判断两个字符串是否是链接的。所以判断点与点之间的关系，需要判断是不是差一个字符，如果差一个字符，那就是有链接。

2、起点和终点的最短路径长度

求起点和终点的最短路径长度，在无权图中，求最短路，用深搜或者广搜就行，没必要用最短路算法。

在无权图中，用广搜求最短路最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

#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;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;
}

105.有向图的完全联通

105. 有向图的完全联通

【题目描述】

给定一个有向图，包含 N 个节点，节点编号分别为 1，2，...，N。现从 1 号节点开始，如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

【输入描述】

第一行包含两个正整数，表示节点数量 N 和边的数量 K。后续 K 行，每行两个正整数 s 和 t，表示从 s 节点有一条边单向连接到 t 节点。

【输出描述】

如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

【输入示例】

【输出示例】

深搜三部曲：

1、确认递归函数，参数

需要传入地图，需要知道当前我们拿到的key，以至于去下一个房间。

同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。

2、确认终止条件

在递归中，本方法处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。

3、处理目前搜索节点出发的路径

本题就没有回溯，本题是需要判断 1节点是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。

什么时候需要回溯操作呢？

当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”，如果不理解的话，去看我写的 0098.所有可达路径的题解。

#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 i:keys){dfs(graph,i,visited);}
}
int main(){int n,m,s,t;cin>>n>>m;vector<list<int>> graph(n+1);while(m--){cin>>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. 岛屿的周长

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。

你可以假设矩阵外均被水包围。在矩阵中恰好拥有一个岛屿，假设组成岛屿的陆地边长都为 1，请计算岛屿的周长。岛屿内部没有水域。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示岛屿的周长。

输入示例

输出示例

遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。

如果该陆地上下左右的空格是有水域，则说明是一条边，

#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;}

查看全文

http://www.lryc.cn/news/610553.html