天涯头条

「代码随想录算法训练营」第四十六天 | 图论 part4

2024-08-26 15:36 由 云雀AC了一整天 发表于 #其他

目录

110. 字符串接龙

题目链接：https://kamacoder.com/problempage.php?pid=1183
文章讲解：https://programmercarl.com/kamacoder/0110.字符串接龙.html
题目状态：看题解

思路：

  1. 输入部分:

    • 读取单词数量 ( n )。
    • 读取起始单词 beginStr 和目标单词 endStr。
    • 读取并存储单词集合 strSet。

  2. 辅助数据结构:

    • visitMap: 记录每个单词是否被访问过，以及路径长度。
    • queue<string> que: 用于广度优先搜索（BFS）的队列。

  3. 算法流程:

    • 将起始单词 beginStr 放入队列，并在 visitMap 中标记路径长度为 1。
    • 使用 BFS 遍历单词：
      • 取出队列的前端单词 word，获取其路径长度 path。
      • 对 word 的每个字符进行替换，生成新单词 newWord。
      • 检查 newWord 是否为目标单词 endStr，如果是，输出路径长度并结束程序。
      • 如果 newWord 在单词集合中且未被访问过，将其加入队列并记录路径长度。

  4. 结束条件:

    • 如果队列为空且未找到目标单词，输出 0。

代码：

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

    // 记录strSet里的字符串是否被访问过，同时记录路径长度
    unordered_map<string, int> visitMap; // <记录的字符串, 路径长度>

    // 初始化队列
    queue<string> que;
    que.push(beginStr);

    // 初始化visitMap
    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';
                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);
                }
            }
        }
    }
    // 没找到输出0
    cout << 0 << endl;
}

105. 有向图的完全可达性

题目链接：https://kamacoder.com/problempage.php?pid=1177
文章讲解：https://programmercarl.com/kamacoder/0105.有向图的完全可达性.html
题目状态：看题解

DFS

思路：

  1. 输入部分:

    • 读取节点数 ( n ) 和边数 ( m )。
    • 读取每条边的起点 ( s ) 和终点 ( t )，构建邻接表 graph。

  2. DFS 函数:

    • 参数:
      • graph: 图的邻接表表示。
      • key: 当前访问的节点。
      • visited: 标记节点是否被访问过的布尔数组。
    • 逻辑:
      • 如果当前节点 key 已访问，直接返回。
      • 标记 key 为已访问。
      • 对于 key 的所有邻接节点，递归调用 dfs。

  3. 主函数:

    • 初始化图的邻接表 graph。
    • 初始化 visited 数组，大小为 ( n+1 )（因为节点编号从 1 开始）。
    • 从节点 1 开始调用 dfs。
    • 检查所有节点是否被访问：
      • 如果有未访问的节点，输出 -1。
      • 如果所有节点都访问过，输出 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;
}

BFS

思路：

  1. 输入部分:

    • 读取节点数 ( n ) 和边数 ( m )。
    • 读取每条边的起点 ( s ) 和终点 ( t )，构建邻接表 graph。

  2. BFS 初始化:

    • 创建一个布尔数组 visited 用于标记节点是否被访问。
    • 从节点 1 开始，标记为已访问，并将其加入队列 que。

  3. BFS 过程:

    • 当队列不为空时，执行以下步骤：
      • 取出队列的前端节点 key。
      • 遍历 key 的所有邻接节点：
        • 如果邻接节点未被访问，将其加入队列并标记为已访问。

  4. 访问检查:

    • 遍历 visited 数组，检查所有节点是否被访问。
    • 如果有未访问的节点，输出 -1。
    • 如果所有节点都访问过，输出 1。

代码：

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

106. 岛屿的周长

题目链接：https://kamacoder.com/problempage.php?pid=1178
文章讲解：https://programmercarl.com/kamacoder/0106.岛屿的周长.html
题目状态：看题解

解法一

思路：

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

遍历整个网格：
如果当前格子是陆地（grid[i][j] == 1），则检查其四周。
使用方向数组计算相邻格子的坐标(x,y)。
如果相邻格子超出边界或者是水域（grid[x][y] == 0），则周长增加 1。

代码：

#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,y
                    if (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;
}

解法二

思路：

计算周长公式。

遍历网格计算总陆地个数。之后计算其周长：

  • 每个陆地格子初始有 4 条边。
  • 每对相邻陆地共享 2 条边。
  • 因此，周长计算为：sum * 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 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;
}