社区讨论
我发现本题还是有一些bug
P3456[POI 2007] GRZ-Ridges and Valleys参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @m4wdgftj
- 此快照首次捕获于
- 2024/12/20 14:30 去年
- 此快照最后确认于
- 2025/11/04 12:36 4 个月前
这一题虽然100分过了,但是我发现数据不是很强,我自己发现有的测试点是过不去的,翻看了题解,还是没有发现有大佬去处理这个问题,先上代码。
CPP#include <bits/stdc++.h>
#define endl "\n"
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
#define N 1005
using namespace std;
int g[N][N], n, ridges, valleys; // g[i][j]为高程图,ridges为山峰数,valleys为山谷数
bool vis[N][N]; // 访问标记数组
queue<pair<int, int>> q; // 队列用于BFS
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1}; // 八个方向的移动
// BFS遍历一个连通块
void bfs(int x, int y)
{
int num = g[x][y]; // 当前点的值
q.push({x, y});
vis[x][y] = true;
bool is_ridge = true, is_valley = true; // 是否是山峰或山谷
while (!q.empty())
{
int cx = q.front().first, cy = q.front().second;
q.pop();
// 遍历8个方向的相邻点
for (int i = 0; i < 8; i++)
{
int nx = cx + dx[i], ny = cy + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n)
{
if (g[nx][ny] > num) // 当前点比联通块高,不可能是山峰
is_ridge = false;
else if (g[nx][ny] < num) // 当前点比联通低块,不可能是山谷
is_valley = false;
else if (g[nx][ny] == num && !vis[nx][ny]) // 当前点和邻接点相同,并且没有访问过
{
vis[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
// 根据遍历的结果确定是否是山峰或山谷
if (is_ridge && !is_valley)
ridges++;
else if (!is_ridge && is_valley)
valleys++;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> g[i][j];
// 遍历所有未访问的点
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (!vis[i][j]) // 如果未访问,执行BFS
bfs(i, j);
if (ridges == 0 && valleys == 0)
cout << "1 1" << endl;
else
// 输出结果
cout << ridges << " " << valleys << endl;
return 0;
}
在上述代码中,如果用以下数据测试,则过不去
输入:
5
1 1 1 1 1
1 2 2 2 1
1 2 3 2 1
1 2 2 2 1
1 1 1 1 1
输出
1 0
在上述数据中,只有一个山峰
输入:
5
3 3 3 3 3 3 2 2 2 3
3 2 1 2 3
3 2 2 2 3
3 3 3 3 3
输出
0 1
在上述数据中,只有一个山谷。
我也想不到什么好办法去处理这样的情况,有没有大佬解决一下
我也想不到什么好办法去处理这样的情况,有没有大佬解决一下
回复
共 2 条回复,欢迎继续交流。
正在加载回复...