思路
这个题的巧妙之处在于如何同时判断搜索的地方是山峰还是山谷。
一开始自己的想法比较笨,把整个图扫2遍,分别求山峰数和山谷数,结果TLE了。
后来发现可以只扫一遍,一开始设置2个flag,默认整个图既是山峰又是山谷。然后遇到违背山谷的条件时,把山谷的flag去掉;山峰同理。这样通过2个flag便可以巧妙地实现同时判断山峰和山谷了。
C++ 代码
#include<iostream>
#include<queue>
#include<string.h>
#include<vector>
using namespace std;
int map[1001][1001];
bool vis[1001][1001];
int dx[] = { -1,-1,-1,0,0,1,1,1 }, dy[] = { -1,0,1,-1,1,-1,0,1 };
int res1, res2;
void bfs(int x, int y, int n)
{
int a, b;
bool high = 0, low = 0;
queue<pair<int, int>> Q;
Q.push({ x,y });
while (Q.size()) {
auto top = Q.front();
Q.pop();
vis[top.first][top.second] = 1;
for (int i = 0; i < 8; i++) {
a = top.first + dx[i], b = top.second + dy[i];
if (a >= 0 && a < n && b >= 0 && b < n) {
if (map[a][b] == map[x][y] && !vis[a][b]) {
vis[a][b] = 1;
Q.push({ a,b });
}
else if (map[a][b] > map[x][y]) {
high = 1; // 不可能是山峰
}
else if (map[a][b] < map[x][y]) {
low = 1; // 不可能是山谷
}
}
}
}
if(!high) res1++;
if(!low) res2++;
}
void cal(int n)
{
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (vis[i][j]) continue;
bfs(i, j, n);
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
}
}
cal(n);
cout << res1 << ' ' << res2 << endl;
return 0;
}