#include using namespace std; const int N = 1010, M = N * N; typedef pair PII; #define x first #define y second int n; int h[N][N]; PII q[M]; bool st[N][N]; /* sx,sy:出发的位置 has_higher,has_lower:是不是周围发现了比自己高的,比自己矮的 */ 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++]; // 利用双重循环遍历周围8连通块 for (int i = t.x - 1; i <= t.x + 1; i++) for (int j = t.y - 1; j <= t.y + 1; j++) { 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() { cin >> n; // 地图 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> h[i][j]; // 山峰个数,山谷个数 int peak = 0, valley = 0; // Flood Fill for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (!st[i][j]) { // 发现新的连通块 bool has_higher = false, has_lower = false; // bfs遍历连通块,标识并且找出这一块是否存在比它高的,比它矮的,使用引用返回多个值 bfs(i, j, has_higher, has_lower); if (!has_higher) peak++; // 没有比自己高的,山峰 if (!has_lower) valley++; // 没有比自己矮的,山谷 // 由于三种情况,山峰,山谷,即不是山峰也不是山谷,所以不能用else } } printf("%d %d\n", peak, valley); return 0; }