AcWing 1106. 山峰和山谷
原题链接
中等
作者:
我是java同学
,
2023-02-07 12:35:07
,
所有人可见
,
阅读 154
bfs
#include <cstring>
#include <algorithm>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n;
int h[N][N];
PII q[M];
bool st[N][N];
void bfs(int sx, int sy, bool &has_higher, bool &has_lower)
{
int hh = 0, tt = -1;
q[++ tt] = {sx, sy};
st[sx][sy] = true;
while (hh <= tt)
{
auto t = q[hh ++ ];
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 = true;
else has_lower = true;
}
else if (!st[i][j])//细节
{
q[ ++ tt] = {i, j};
st[i][j] = true;
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &h[i][j]);
int peak = 0, valley = 0;
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 ++ ;
}
printf("%d %d\n", peak, valley);
return 0;
}