106. 岛屿的周长
题目链接
文章讲解
思路：
遍历矩阵：遍历每个陆地块（即值为 1 的单元格）。
计算每个陆地块的边界：对于每个 1，检查它的上下左右四个方向：
如果相邻的方向是 0（水）或者是矩阵的边界，则该方向贡献 1 到周长。
如果相邻的方向是 1（陆地），则不贡献周长，因为已经通过相邻陆地共享边界。
最终得到总周长：通过遍历矩阵的每个 1 来累计周长。
#include<bits/stdc++.h>
using namespace std;
// 方向数组：右，下，左，上
// 格式：[dx, dy]，表示水平方向和垂直方向的偏移量
int direct[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
int sum = 0; // 用于记录岛屿的周长
// 广度优先搜索（BFS）函数，用于遍历连通区域
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visit, int x, int y) {
queue<pair<int, int>> q; // 队列，用于 BFS 遍历
q.push({x, y}); // 将起始点加入队列
visit[x][y] = true; // 标记起始点已访问
// 当队列不为空时继续遍历
while (!q.empty()) {
pair<int, int> cur = q.front(); // 取出队列的第一个元素
q.pop(); // 移除队列的第一个元素
int curx = cur.first; // 当前点的 x 坐标
int cury = cur.second; // 当前点的 y 坐标
// 遍历四个方向（右，下，左，上）
for (int i = 0; i < 4; i++) {
int nextx = curx + direct[i][0]; // 计算下一个 x 坐标
int nexty = cury + direct[i][1]; // 计算下一个 y 坐标
// 如果下一个位置越界，跳过该位置并增加周长
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) {
sum++; // 增加周长
} else {
// 如果该位置是陆地且未访问过
if (grid[nextx][nexty] == 1 && !visit[nextx][nexty]) {
q.push({nextx, nexty}); // 将新的陆地位置加入队列
visit[nextx][nexty] = true; // 标记该位置为已访问
}
// 如果该位置是水域，增加周长
else if (grid[nextx][nexty] == 0) {
sum++; // 增加周长
}
}
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入网格的行数和列数
// 初始化网格和访问标记数组
vector<vector<int>> grid(n, vector<int>(m, 0)); // 网格，0表示水域，1表示陆地
vector<vector<bool>> visit(n, vector<bool>(m, false)); // 访问标记数组，初始为未访问
// 输入网格的数据
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> grid[i][j]; // 输入每个位置的值（0 或 1）
}
}
// 对每个陆地进行 BFS 遍历
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果当前位置是陆地且未访问过，则调用 bfs 函数
if (grid[i][j] == 1 && !visit[i][j]) {
bfs(grid, visit, i, j);
}
}
}
// 输出计算得到的岛屿的周长
cout << sum;
}
110. 字符串接龙
#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.有向图的完全联通
dfs
#include<bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>>& grid,vector<bool>& visited,int x,int n)
{
for(int i=1;i<=n;i++)
{
if(grid[x][i]==1&&!visited[i])
{
visited[i]=true;
dfs(grid,visited,i,n);
}
}
}
int main() {
int n, k;
cin >> n >> k; // 输入节点数和边的数量
// 初始化图的邻接矩阵和访问数组
vector<vector<int>> grid(n + 1, vector<int>(n + 1, 0)); // 邻接矩阵，0表示没有边，1表示有边
vector<bool> visited(n + 1, false); // 访问标记数组
// 输入每条边，更新图的邻接矩阵
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y; // 输入每条边的起点和终点
grid[x][y] = 1; // 从节点 x 到节点 y 有一条有向边
}
dfs(grid,visited,1,n);
// 检查是否所有节点都被访问过
for (int i = 2; i <= n; i++) {
if (!visited[i]) { // 如果有节点没有被访问到，输出 -1
cout << -1;
return 0; // 提前结束程序
}
}
// 如果所有节点都被访问到，输出 1
cout << 1;
return 0;
}
bfs
#include<bits/stdc++.h>
using namespace std;
// 方向数组：右，下，左，上（这里不是用到）
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
void bfs(vector<vector<int>>& grid, vector<bool>& visited, int start) {
queue<int> que;
que.push(start); // 从节点 1 开始
visited[start] = true;
while (!que.empty()) {
int cur = que.front();
que.pop();
// 遍历所有邻接节点
for (int i = 1; i < grid.size(); i++) {
if (grid[cur][i] == 1 && !visited[i]) { // 如果从 cur 到 i 有边，并且 i 节点没被访问过
visited[i] = true;
que.push(i);
}
}
}
}
int main() {
int n, k;
cin >> n >> k; // 输入节点数和边的数量
// 初始化图的邻接矩阵和访问数组
vector<vector<int>> grid(n + 1, vector<int>(n + 1, 0)); // 邻接矩阵，0表示没有边，1表示有边
vector<bool> visited(n + 1, false); // 访问标记数组
// 输入每条边，更新图的邻接矩阵
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y; // 输入每条边的起点和终点
grid[x][y] = 1; // 从节点 x 到节点 y 有一条有向边
}
// 使用 BFS 从节点 1 开始遍历
bfs(grid, visited, 1);
// 检查是否所有节点都被访问过
for (int i = 2; i <= n; i++) {
if (!visited[i]) { // 如果有节点没有被访问到，输出 -1
cout << -1;
return 0; // 提前结束程序
}
}
// 如果所有节点都被访问到，输出 1
cout << 1;
return 0;
}