代码随想录算法训练营 Day53 图论Ⅳ 字符串接龙 有向图 岛屿周长

图论

题目

110. 字符串接龙
给出开始与结束的字符串，给出字符串 list，返回从字符串开始到结束过程中最短的路径
难点在于：求出发点与尽头的最短路径，通过广度优先搜刮实现
对原始的字符串逐个位进行替换，匹配是否出现在 list 中，出现了就记录到 map 中，直到找到字符
在无权图中，用广搜求最短路最为合适，广搜只要搜到了尽头，那么肯定是最短的路径。因为广搜就是以出发点中心向附近扩散的搜刮。
本题如果用深搜，会比力麻烦，要在到达尽头的不同路径中选则一条最短路。

1. #include <iostream>
2. #include <vector>
3. #include <unordered_map>
4. #include <unordered_set>
5. #include <string>
6. #include <queue>
8. using namespace std;
10. int main() {
11.     // 数据处理
12.     int n;
13.     string beginStr, endStr, str;
14.     unordered_set<string> strSet;
15.     cin >> n;
16.     cin >> beginStr >> endStr;
17.     for (int i = 0; i < n; ++i) {
18.         cin >> str;
19.         strSet.insert(str);
20.     }
22.     // 记录访问情况
23.     unordered_map<string, int> vis;
24.     queue<string> que;
25.     que.push(beginStr);
26.     vis.insert(make_pair(beginStr, 1));
28.     // 广度优先搜索遍历
29.     while (!que.empty()) {
30.         string word = que.front();
31.         que.pop();
32.         // 记录路径长度
33.         int path = vis[word];
35.         for (int i = 0; i < word.size(); ++i) {
36.             string newWord = word;
37.             for (int j = 0; j < 26; ++j) {
38.                 newWord[i] = j + 'a';
39.                 // 经过变换到达了目标字符
40.                 if (newWord == endStr) {
41.                     cout << path + 1 << endl;
42.                     return 0;
43.                 }
44.                 // 记录字符变化过程
45.                 if (strSet.find(newWord) != strSet.end() && vis.find(newWord) == vis.end()) {
46.                     vis.insert({newWord, path+1});
47.                     que.push(newWord);
48.                 }
49.             }
50.         }
51.     }
52.     // 找不到变换路径
53.     cout << 0 << endl;
54. }

复制代码

105. 有向图的完全联通
有向图的连通性判定，判定 1 是否可以到达所有节点
思路就是构造有向图，然后遍历图标记节点为 vis 为 true，最后遍历节节点，全为 true 则阐明可访问

1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. #include <list>
6. using namespace std;
8. void dfs(vector<list<int>>& graph, vector<bool>& vis, int idx) {
9.     if (vis[idx]) return;
10.     vis[idx] = true;
11.     for (int key : graph[idx]) {
12.         dfs(graph, vis, key);
13.     }
14. }
16. // 需要预先处理vis[1] = ture
17. void dfs2(vector<list<int>>& graph, vector<bool>& vis, int idx) {
18.     for (int key : graph[idx]) {
19.         if (!vis[idx]) {
20.             vis[idx] = true;
21.             dfs(graph, vis, key);
22.         }
23.     }
24. }
26. void bfs(vector<list<int>>& graph, vector<bool>& vis) {
27.     queue<int> que;
28.     que.push(1);
29.     vis[1] = true;
31.     while (!que.empty()) {
32.         list<int> lists = graph[que.front()];
33.         que.pop();
34.         for (int key: lists) {
35.             if (!vis[key]) {
36.                 vis[key] = true;
37.                 que.push(key);
38.             }
39.         }
40.     }
41. }
44. int main() {
45.     // 构造图结构
46.     int n, k;
47.     cin >> n >> k;
48.     // 使用邻接表构造
49.     vector<list<int>> graph(n+1);
50.     vector<bool> vis(n+1, false);
51.     for (int i = 0; i < k; ++i) {
52.         int s, t;
53.         cin >> s >> t;
54.         graph[s].push_back(t);
55.     }
57.     // 遍历图并检查是否完全访问
58.     bfs(graph, vis);
59.     // dfs(graph, vis, 1);
60.     for (int i = 1; i < n; ++i) {
61.         if (!vis[i]) {
62.             cout << -1 <<endl;
63.             return 0;
64.         }
65.     }
66.     cout << 1 << endl;
67.     return 0;
68. }

复制代码

106. 岛屿的周长
岛屿周长不需要 DFS or BFS 只需要判定当前岛的附近如果是海洋大概是边界 +1 即可
有些岛屿题没那么难

1. #include <iostream>
2. #include <vector>
4. using namespace std;
6. int main() {
7.     // 输入处理
8.     int n,m;
9.     cin >> n >> m;
10.     vector<vector<int>> grid(n, vector<int>(m, 0));
11.     for (int i = 0; i < n; ++i) {
12.         for (int j = 0; j < m; ++j) {
13.             cin >> grid[i][j];
14.         }
15.     }
17.     // 遍历计算周长
18.     int res = 0;
19.     int dir[4][2] = {0,-1,-1,0,0,1,1,0};
20.     for (int i = 0; i < n; ++i) {
21.         for (int j = 0; j < m; ++j) {
22.             // 找到陆地
23.             if (grid[i][j] == 1) {
24.                 for (int k = 0; k < 4; ++k) {
25.                     int nextX = i + dir[k][0];
26.                     int nextY = j + dir[k][1];
27.                     if (nextX < 0 || nextX >= n || nextY < 0 || nextY >= m || grid[nextX][nextY] == 0) res++;
28.                 }
29.             }
30.         }
31.     }
32.     cout << res << endl;
33.     return 0;
34. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告