DFS
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1010;
int h[N][N];
bool st[N][N];
int n;
int peak, valley;
bool has_higher, has_lower;
void dfs(int x, int y)
{
if (st[x][y])
{
return;
}
st[x][y] = true;
for (int i = x - 1; i <= x + 1; i++)
{
for (int j = y - 1; j <= y + 1; j++)
{
if (i < 0 || i >= n || j < 0 || j >= n)
{
continue;
}
if (i == x && j == y)
{
continue;
}
if (h[i][j] > h[x][y])
{
has_higher = true;
}
else if (h[i][j] < h[x][y])
{
has_lower = true;
}
else
{
dfs(i, j);
}
}
}
}
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> h[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (!st[i][j])
{
dfs(i, j);
if (!has_higher)
{
peak++;
}
if (!has_lower)
{
valley++;
}
has_higher = has_lower = false;
}
}
}
cout << peak << ' ' << valley << endl;
return 0;
}
BFS
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1010;
int h[N][N];
bool st[N][N];
int n;
int peak, valley;
void bfs(int x, int y, bool &has_higher, bool &has_lower)
{
queue<PII> q;
q.push({x, y});
st[x][y] = true;
while (q.size())
{
PII t = q.front();
q.pop();
for (int i = t.x - 1; i <= t.x + 1; i++)
{
for (int j = t.y - 1; j <= t.y + 1; j++)
{
if (i == t.x && j == t.y)
{
continue;
}
if (i < 0 || i >= n || j < 0 || j >= n)
{
continue;
}
if (h[i][j] != h[t.x][t.y]) // 判断是否是山脉的边界;
{
if (h[i][j] > h[t.x][t.y])
{
has_higher = 1;
}
if (h[i][j] < h[t.x][t.y])
{
has_lower = 1;
}
}
else if (!st[i][j])
{
q.push({i, j});
st[i][j] = 1;
}
// 不能修改为下面的代码;
// 如果当前区域周围有一个已经被搜索过的比该区域更高或更矮的区域,按照下面的逻辑,has_higher与has_lower不会被更新;
// if (st[i][j])
// {
// continue;
// }
// if (h[i][j] > h[t.x][t.y])
// {
// has_higher = true;
// }
// else if (h[i][j] < h[t.x][t.y])
// {
// has_lower = true;
// }
// else
// {
// q.push({i, j});
// st[i][j] = true;
// }
}
}
}
}
signed main(void)
{
std::ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> h[i][j];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (!st[i][j])
{
bool has_higher = false, has_lower = false;
bfs(i, j, has_higher, has_lower);
if (!has_higher)
{
peak++;
}
if (!has_lower)
{
valley++;
}
has_higher = has_lower = false;
}
}
}
cout << peak << ' ' << valley << endl;
return 0;
}