DFS
2025-09-12 22:09:31
发布于:湖北
8阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
// 定义四个方向的位移:右、下、左、上
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
// 存储所有干草堆的坐标
set<pair<int, int>> points;
// 记录已经访问过的坐标,避免重复计算
set<pair<int, int>> visited;
// 周长计数器
int perimeter = 0;
// DFS函数,用于遍历连通块并计算周长
void dfs(int x, int y) {
// 如果当前坐标已经访问过,直接返回
if (visited.find({x, y}) != visited.end()) {
return;
}
// 标记当前坐标为已访问
visited.insert({x, y});
// 遍历四个方向
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
// 如果相邻格子是空的(没有干草堆),则周长加1
if (points.find({nx, ny}) == points.end()) {
perimeter++;
} else {
// 否则,递归访问相邻的干草堆
dfs(nx, ny);
}
}
}
int main() {
int n;
cin >> n;
// 读取所有干草堆的坐标并存入集合
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
points.insert({x, y});
}
// 从集合中的第一个点开始DFS遍历
auto start = *points.begin();
dfs(start.first, start.second);
// 输出周长
cout << perimeter << endl;
return 0;
}
这里空空如也


有帮助,赞一个