110. 字符串接龙
题目链接：https://kamacoder.com/problempage.php?pid=1183
文章讲解：https://programmercarl.com/kamacoder/0110.字符串接龙.html
题目状态：看题解
思路：
-
输入部分:
- 读取单词数量 ( n )。
- 读取起始单词
beginStr和目标单词endStr。 - 读取并存储单词集合
strSet。
-
辅助数据结构:
visitMap: 记录每个单词是否被访问过，以及路径长度。queue<string> que: 用于广度优先搜索（BFS）的队列。
-
算法流程:
- 将起始单词
beginStr放入队列，并在visitMap中标记路径长度为 1。 - 使用 BFS 遍历单词：
- 取出队列的前端单词
word，获取其路径长度path。 - 对
word的每个字符进行替换，生成新单词newWord。 - 检查
newWord是否为目标单词endStr，如果是，输出路径长度并结束程序。 - 如果
newWord在单词集合中且未被访问过，将其加入队列并记录路径长度。
- 取出队列的前端单词
- 将起始单词
-
结束条件:
- 如果队列为空且未找到目标单词，输出 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
思路：
-
输入部分:
- 读取节点数 ( n ) 和边数 ( m )。
- 读取每条边的起点 ( s ) 和终点 ( t )，构建邻接表
graph。
-
DFS 函数:
- 参数:
graph: 图的邻接表表示。key: 当前访问的节点。visited: 标记节点是否被访问过的布尔数组。
- 逻辑:
- 如果当前节点
key已访问，直接返回。 - 标记
key为已访问。 - 对于
key的所有邻接节点，递归调用dfs。
- 如果当前节点
- 参数:
-
主函数:
- 初始化图的邻接表
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
思路：
-
输入部分:
- 读取节点数 ( n ) 和边数 ( m )。
- 读取每条边的起点 ( s ) 和终点 ( t )，构建邻接表
graph。
-
BFS 初始化:
- 创建一个布尔数组
visited用于标记节点是否被访问。 - 从节点 1 开始，标记为已访问，并将其加入队列
que。
- 创建一个布尔数组
-
BFS 过程:
- 当队列不为空时，执行以下步骤：
- 取出队列的前端节点
key。 - 遍历
key的所有邻接节点：- 如果邻接节点未被访问，将其加入队列并标记为已访问。
- 取出队列的前端节点
- 当队列不为空时，执行以下步骤：
-
访问检查:
- 遍历
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;
}