社区讨论

我发现本题还是有一些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 条回复,欢迎继续交流。

正在加载回复...