代码随想录算法训练day59---图论系列4
代码随想录算法训练
—day59
文章目录
- 代码随想录算法训练
- 前言
- 一、110.字符串接龙
- 二、105.有向图的完全可达性
- dfs版本1
- dfs版本2
- bfs版本
- 三、100. 岛屿的最大面积
- 方法一
- 方法二
- 总结
前言
今天是算法营的第59天，希望自己能够坚持下来！
今天继续图论part！今日任务：
● 110.字符串接龙
● 105.有向图的完全可达性
● 106.岛屿的周长
一、110.字符串接龙
卡码网题目链接
leetcode题目链接
文章讲解
思路：
从 startStr 到 endStr，找在 strList 中最短的路径，本题只需要求出最短路径的长度就可以了，不用找出具体路径。
所以这道题要解决两个问题：
- 图中的线是如何连在一起的
- 起点和终点的最短路径长度
1.由题目可得，strList中的字符串是以“ 只变化一个字符“作为连接
2.并且适合用广搜，因为广搜只要到达终点就是最短距离
另外需要有一个注意点：
- 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环
- 使用set来检查字符串是否出现在字符串集合里更快一些
代码如下：
#include<iostream>
#include<unordered_set>
#include<unordered_map>
#include<queue>
#include<string>
using namespace std;
//需要求最短距离，适合用广度优先搜索
//strList中的字符串是以“ 只变化一个字符“作为连接
int main() {
int n;
string beginStr, endStr, str;
cin >> n;
cin >> beginStr >> endStr;
unordered_set<string> strSet; //用set方便查找
while (n--) {
cin >> str;
strSet.insert(str);
}
//记录strSet里的字符串是否被访问过，同时记录路径长度
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]; //这个字符串在路径中的长度
//开始在这个str中，挨个字符去替换
for (int i = 0; i < word.size(); i++) {
string newWord = word; //用一个新字符串替换str，因为每次要置换一个字符
//遍历26字母
for(int j = 0; j < 26; j++) {
newWord[i] = j + 'a'; //从a开始换，替换掉str的第i个字母
if (newWord == endStr) { //替换字母后，与重点字符串相同
cout << path + 1 << endl; //找到路径了
return 0;
}
//字符串集合中有newWord,并且newWord没有被访问过
if (strSet.find(newWord) != strSet.end() && visitMap.find(newWord) == visitMap.end()) {
visitMap[newWord] = path + 1; //添加访问信息
que.push(newWord); //将新字符串放到队列中
}
}
}
}
//没找到路径，输出0
cout << 0 << endl;
}
二、105.有向图的完全可达性
卡码网题目链接
文章讲解
思路：
本题是一个有向图搜索全路径的问题。只能用深搜（DFS）或者广搜（BFS）来搜。
深搜三部曲：
1.确认递归函数，参数：需要地图，当前位置，标记访问过的位置的数组
2.确认终止条件：递归函数可以是处理当前节点，也可以是处理下一个节点。根据不同的写法有不同的终止条件。我这里是按照当前节点来写。那么终止条件就是当前节点已经访问过了，所以直接返回。
3.处理目前搜索节点出发的路径：处理当前路径就是对当前路径标记成true，并且找到下一个路径
注意：这里不需要回溯，因为题目求的是需要到达所有的节点，不需要退回标记。而回溯是找不同的路径时，到了终点需要掉头的时候就需要回溯，才能得出一条条不一样的路。
dfs版本1
代码如下：
// 写法一：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;
// 节点编号从1到n，所以申请 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;
}
dfs版本2
第二种写法注意有注释的地方是和写法一的区别：
写法二：dfs处理下一个要访问的节点
#include <iostream>
#include <vector>
#include <list>
using namespace std;
void dfs(const vector<list<int>>& graph, int key, vector<bool>& visited) {
list<int> keys = graph[key];
for (int key : keys) {
if (visited[key] == false) { // 确认下一个是没访问过的节点
visited[key] = true;
dfs(graph, key, 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);
visited[1] = true; // 节点1 预先处理
dfs(graph, 1, visited);
for (int i = 1; i <= n; i++) {
if (visited[i] == false) {
cout << -1 << endl;
return 0;
}
}
cout << 1 << endl;
}
bfs版本
#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
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);
visited[1] = true; // 1 号房间开始
queue<int> que;
que.push(1); // 1 号房间开始
// 广度优先搜索的过程
while (!que.empty()) {
int key = que.front(); que.pop();
list<int> keys = graph[key];
for (int key : keys) {
if (!visited[key]) {
que.push(key);
visited[key] = true;
}
}
}
for (int i = 1; i <= n; i++) {
if (visited[i] == false) {
cout << -1 << endl;
return 0;
}
}
cout << 1 << endl;
}
三、100. 岛屿的最大面积
卡码网题目链接
leetcode题目链接
文章讲解
方法一
遍历每一个空格，遇到岛屿则计算其上下左右的空格情况。
当岛屿周边是边界或者是水域的话，说明找到了一条边。
代码如下：
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
int dir[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 (graph[i][j] == 1) {
//遍历岛屿四周
for (int k = 0; k < 4; k++) {
int x = i + dir[k][0];
int y = j + dir[k][1];
//xy位置在边界上，或者是水域，则周长+1
if (x < 0
|| x >= n
|| y < 0
|| y >= m
|| graph[x][y] == 0) {
result++;
}
}
}
}
}
cout << result << endl;
}
方法二
假设一个岛屿有4条边，
有一对相邻两个陆地，边的总数就要减2，
那么result = 岛屿数量 * 4 - cover * 2;
代码如下：
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
}
}
int sum = 0; //陆地数量
int cover = 0; //相邻数量
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (graph[i][j] == 1) {
sum++;
//统计当前岛屿左边相邻陆地
if (i-1 >= 0 && graph[i-1][j] == 1) cover++;
//统计当前岛屿左边相邻陆地
if(j-1 >= 0 && graph[i][j-1] == 1) cover++;
//不需要统计下边和右边，因为会重复计算
}
}
}
//岛屿周长= 岛屿数量*4 - 相邻的岛屿数*2
cout << sum*4 - 2*cover << endl;
}
总结
- 字符串接龙 ：求最短路径，考虑用广搜。根据题意可知节点的连接是“只替换一个字符”，遍历字符串，再分别替换成26字母，并用set检查是否在list中。
- 有向图的完全可达性：需要有一个数组来记录到达过的路径，注意这里不需要回溯。
- 岛屿的最大面积：方法一：岛屿周围是水或者边界就是边长 方法二：周长= 岛屿数量4 - 相邻的岛屿数2
明天继续加油！