#include 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; }