BFS和DFS两种解法

#include <iostream>
#include <queue>

using namespace std;

static constexpr int dirs[][2] { {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1} };

const int N = 1005;
int grid[N][N], visited[N][N];

int n;
bool is_peak, is_valley;

void bfs(int sx, int sy) {
  queue<pair<int, int>> q;
  q.emplace(sx, sy);
  visited[sy][sx] = 1;

  while (not q.empty()) {
    const auto [x, y] = q.front(); q.pop();
    for (const auto& d : dirs) {
      int nx = x + d[0], ny = y + d[1];
      if (nx < 1 || ny < 1 || nx > n || ny > n)
        continue;
      if (grid[ny][nx] > grid[y][x]) is_peak = false;
      else if (grid[ny][nx] < grid[y][x]) is_valley = false;
      if (grid[ny][nx] != grid[y][x] || visited[ny][nx]) continue;
      q.emplace(nx, ny);
      visited[ny][nx] = 1;
    }
  }
}

void dfs(int x, int y) {
  visited[y][x] = 1;
  for (const auto& d : dirs) {
    int nx = x + d[0], ny = y + d[1];
    if (nx < 1 || ny < 1 || nx > n || ny > n)
      continue;
    if (grid[ny][nx] > grid[y][x]) is_peak = false;
    else if (grid[ny][nx] < grid[y][x]) is_valley = false;

    if (grid[ny][nx] != grid[y][x] || visited[ny][nx]) continue;
    dfs(nx, ny);
  }
}

int main(void) {
  scanf("%d", &n);
  for (int y = 1; y <= n; ++y)
    for (int x = 1; x <= n; ++x) cin >> grid[y][x];

  int peaks = 0, valleys = 0;
  for (int y = 1; y <= n; ++y)
    for (int x = 1; x <= n; ++x) {
      if (visited[y][x]) continue;
      is_peak = true, is_valley = true;
      bfs(x, y);
      // dfs(x, y); // Memory Limit Exceeded
      peaks += is_peak, valleys += is_valley;
    }

  printf("%d %d\n", peaks, valleys);
  return 0;
}