leetcode-go/bailian/1088.ski/main.cc

#include <algorithm>
#include <cstdio>

using namespace std;

const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

const int N = 100;
int h[N][N], dp[N][N];

struct Grid {
  int r;
  int c;
  int h;
  bool operator<(const Grid &that) const { return this->h < that.h; }
};

Grid area[N * N];

int main() {
  int R, C;
  scanf("%d %d", &R, &C);
  for (int i = 0, k = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
      scanf("%d", &h[i][j]);
      dp[i][j] = 1;
      area[k++] = {i, j, h[i][j]};
    }
  }
  sort(area, area + R * C);
  int len = 1;
  for (int i = 0; i < R * C; i++) {
    Grid g = area[i];
    for (int j = 0; j < 4; j++) {
      int nx = g.r + dx[j], ny = g.c + dy[j];
      if (0 <= nx && nx < R && 0 <= ny && ny < C && g.h < h[nx][ny]) {
        dp[nx][ny] = max(dp[nx][ny], dp[g.r][g.c] + 1);
        len = max(len, dp[nx][ny]);
      }
    }
  }
  printf("%d\n", len);
  return 0;
}