|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 1010;
|
|
|
const int M = N * N;
|
|
|
|
|
|
int n;
|
|
|
|
|
|
int h[N][N];
|
|
|
int st[M][2]; // 第一维：并查集编号，第二维：0:附近的最小值，1：附近的最大值
|
|
|
|
|
|
// 1692 ms
|
|
|
// 8个方向
|
|
|
int dx[] = {0, 0, -1, 1, -1, 1, -1, 1}; // 上下左右
|
|
|
int dy[] = {1, -1, 0, 0, 1, 1, -1, -1}; // 左下，右下，左上，右上
|
|
|
|
|
|
int p[M];
|
|
|
int find(int x) {
|
|
|
if (p[x] != x) p[x] = find(p[x]);
|
|
|
return p[x];
|
|
|
}
|
|
|
|
|
|
// 根据坐标获取并查集的编号
|
|
|
void getXy(int num, int &x, int &y) {
|
|
|
x = (num - 1) / n + 1;
|
|
|
y = (num - 1) % n + 1;
|
|
|
}
|
|
|
// 根据并查集的编号获取坐标
|
|
|
int getNum(int x, int y) {
|
|
|
return (x - 1) * n + y;
|
|
|
}
|
|
|
|
|
|
int valley, peak;
|
|
|
int main() {
|
|
|
// 初始化并查集
|
|
|
// i为每个格子在并查集中的编号，编号策略为 (i-1)*n+j
|
|
|
for (int i = 0; i < M; i++) p[i] = i; // 每个人都是自己的祖先
|
|
|
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
for (int j = 1; j <= n; j++) {
|
|
|
cin >> h[i][j];
|
|
|
int num = getNum(i, j);
|
|
|
st[num][0] = st[num][1] = h[i][j]; // 初始化
|
|
|
}
|
|
|
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
for (int j = 1; j <= n; j++)
|
|
|
for (int k = 0; k < 8; k++) {
|
|
|
int x = i + dx[k], y = j + dy[k];
|
|
|
if (x == 0 || y == 0 || x > n || y > n) continue;
|
|
|
// 编号
|
|
|
int a = getNum(i, j);
|
|
|
int b = getNum(x, y);
|
|
|
// 族长
|
|
|
int pa = find(a), pb = find(b);
|
|
|
|
|
|
// 记录我们家族周围最小的
|
|
|
if (h[i][j] > h[x][y]) st[pa][0] = min(st[pa][0], h[x][y]);
|
|
|
// 记录我们家族周围最大的
|
|
|
if (h[i][j] < h[x][y]) st[pa][1] = max(st[pa][1], h[x][y]);
|
|
|
|
|
|
if (h[i][j] == h[x][y]) {
|
|
|
if (pa != pb) { // 合并并查集
|
|
|
p[pa] = pb;
|
|
|
st[pb][0] = min(st[pb][0], st[pa][0]);
|
|
|
st[pb][1] = max(st[pb][1], st[pa][1]);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
// 没有比自己高的，山峰
|
|
|
// 没有比自己矮的，山谷
|
|
|
for (int i = 1; i <= n * n; i++) {
|
|
|
if (p[i] == i) {
|
|
|
int x, y;
|
|
|
getXy(i, x, y);
|
|
|
if (st[i][0] == h[x][y]) valley++;
|
|
|
if (st[i][1] == h[x][y]) peak++;
|
|
|
}
|
|
|
}
|
|
|
printf("%d %d\n", peak, valley);
|
|
|
return 0;
|
|
|
} |
