代码随想录算法训练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); //将新字符串放到队列中}}}}//没找到路径，输出0cout << 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位置在边界上，或者是水域，则周长+1if (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 - 相邻的岛屿数*2cout << sum*4 - 2*cover << endl;
}