代码随想录算法训练营第五十三天|Day53 图论

字符串接龙

https://www.programmercarl.com/kamacoder/0110.%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%8E%A5%E9%BE%99.html

思路

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX 1000 // 假设最大字符串数
#define WORD_LENGTH 100 // 假设每个单词的最大长度typedef struct {char words[MAX][WORD_LENGTH]; // 保存字符串int size; // 当前字符串数量
} StringSet;typedef struct {char words[MAX][WORD_LENGTH]; // 保存字符串int length[MAX]; // 保存路径长度int front, rear; // 队列头尾指针
} Queue;void initStringSet(StringSet *set) {set->size = 0;
}void addString(StringSet *set, const char *word) {strcpy(set->words[set->size++], word);
}int contains(StringSet *set, const char *word) {for (int i = 0; i < set->size; i++) {if (strcmp(set->words[i], word) == 0) {return 1; // 存在}}return 0; // 不存在
}void initQueue(Queue *q) {q->front = 0;q->rear = 0;
}void enqueue(Queue *q, const char *word, int pathLength) {strcpy(q->words[q->rear], word);q->length[q->rear] = pathLength;q->rear++;
}void dequeue(Queue *q, char *word, int *pathLength) {strcpy(word, q->words[q->front]);*pathLength = q->length[q->front];q->front++;
}int isEmpty(Queue *q) {return q->front == q->rear;
}int main() {int n;scanf("%d", &n);char beginStr[WORD_LENGTH], endStr[WORD_LENGTH];scanf("%s %s", beginStr, endStr);StringSet strSet;initStringSet(&strSet);for (int i = 0; i < n; i++) {char str[WORD_LENGTH];scanf("%s", str);addString(&strSet, str);}Queue que;initQueue(&que);enqueue(&que, beginStr, 1); while (!isEmpty(&que)) {char word[WORD_LENGTH];int pathLength;dequeue(&que, word, &pathLength);for (int i = 0; i < strlen(word); i++) {char newWord[WORD_LENGTH];strcpy(newWord, word); for (char j = 'a'; j <= 'z'; j++) {newWord[i] = j; if (strcmp(newWord, endStr) == 0) {printf("%d\n", pathLength + 1);return 0;}if (contains(&strSet, newWord)) {enqueue(&que, newWord, pathLength + 1);}}}}printf("0\n");return 0;
}

学习反思

代码是一个可以计算字符串变换路径长度的程序，根据输入的起始字符串和目标字符串，通过变换每个字符的方式，计算出从起始字符串到目标字符串的最短变换路径长度。代码中使用了两个数据结构StringSet和Queue来实现功能。StringSet用于保存输入的字符串集合，Queue用于保存待处理的字符串和路径长度。代码的主要逻辑是通过BFS（广度优先搜索）算法遍历所有可能的变换路径。代码中使用了一些函数来实现各种操作，例如initStringSet用于初始化StringSet，addString用于向StringSet中添加字符串，contains用于判断StringSet中是否包含某个字符串。类似地，initQueue用于初始化Queue，enqueue用于入队，dequeue用于出队，isEmpty用于判断Queue是否为空。在主函数中，首先读取输入的字符串数量n和起始字符串和目标字符串beginStr、endStr。然后利用循环读取n个字符串，并将它们添加到StringSet中。接下来，初始化Queue，并将起始字符串和路径长度1入队。然后进入循环，直到队列为空，从队列中取出一个字符串和路径长度，然后对该字符串的每个字符进行变换，生成新的字符串，判断是否与目标字符串相等，如果相等则输出路径长度并结束程序。如果不相等，则判断新生成的字符串是否在StringSet中存在，如果存在则将其入队，并增加路径长度。循环结束后，如果没有找到路径，则输出0。

有向图的完全可达性

https://www.programmercarl.com/kamacoder/0105.%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E5%AE%8C%E5%85%A8%E5%8F%AF%E8%BE%BE%E6%80%A7.html

思路

#include <stdio.h>
#include <stdlib.h>#define MAX_NODES 101 // 节点编号范围 [1, N]
#define MAX_EDGES 2000 // 最大边数typedef struct {int edges[MAX_NODES][MAX_NODES]; // 邻接矩阵表示图int visited[MAX_NODES]; // 访问标记int n; // 节点数
} Graph;void initGraph(Graph *g, int n) {g->n = n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {g->edges[i][j] = 0; }g->visited[i] = 0; }
}
void addEdge(Graph *g, int s, int t) {g->edges[s][t] = 1; 
}
void dfs(Graph *g, int v) {g->visited[v] = 1; for (int i = 1; i <= g->n; i++) {if (g->edges[v][i] == 1 && !g->visited[i]) { dfs(g, i); }}
}int main() {int n, k; scanf("%d %d", &n, &k);Graph g;initGraph(&g, n);for (int i = 0; i < k; i++) {int s, t;scanf("%d %d", &s, &t);addEdge(&g, s, t); }dfs(&g, 1);for (int i = 1; i <= n; i++) {if (!g.visited[i]) { printf("-1\n"); return 0;}}printf("1\n"); return 0;
}

学习反思

实现了一个无向图的深度优先搜索，用于判断图是否是连通图。

代码的主要逻辑如下：

1. 首先定义了一个Graph结构体，包含了邻接矩阵表示的图的边和节点信息。
2. initGraph函数初始化了图的边和节点信息。
3. addEdge函数用于向图中添加一条边。
4. dfs函数实现了深度优先搜索算法，其中使用了递归的方式进行搜索，如果找到一个节点未被访问过，则递归调用dfs继续搜索。
5. main函数中首先读取输入的节点数和边数，然后根据输入的边信息构建图。接着调用dfs函数进行深度优先搜索，并根据搜索结果判断图是否是连通图。

岛屿的周长

https://www.programmercarl.com/kamacoder/0106.%E5%B2%9B%E5%B1%BF%E7%9A%84%E5%91%A8%E9%95%BF.html

思路

#include <stdio.h>
#define MAX_SIZE 50
int main() {int n, m;int matrix[MAX_SIZE][MAX_SIZE];int perimeter = 0;scanf("%d %d", &n, &m);for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%d", &matrix[i][j]);}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (matrix[i][j] == 1) {// 上if (i == 0 || matrix[i - 1][j] == 0) perimeter++;// 下if (i == n - 1 || matrix[i + 1][j] == 0) perimeter++;// 左if (j == 0 || matrix[i][j - 1] == 0) perimeter++;// 右if (j == m - 1 || matrix[i][j + 1] == 0) perimeter++;}}}printf("%d\n", perimeter);    return 0;
}

学习反思

用来计算一个由0和1组成的矩阵的周长的。输入包括两个整数n和m，表示矩阵的行数和列数，然后根据输入的n和m读取矩阵的元素。如果矩阵中的某个元素为1，则计算该元素所在位置的周围四个方向的元素，如果是0或者超出矩阵边界，则周长+1。最后输出计算得到的周长。其中使用了一个宏定义MAX_SIZE来定义矩阵的最大大小，防止数组越界。通过两个循环来依次读取矩阵的元素，并通过四个判断语句来计算周长。代码的主要思路是遍历矩阵的每个元素，如果当前元素是1，则计算周围四个方向的元素，如果是0或者超出边界，则周长+1。最后输出周长。该代码的时间复杂度为O(n*m)，其中n和m分别是矩阵的行数和列数。