111 lines
2.3 KiB
C++
111 lines
2.3 KiB
C++
#include <algorithm>
|
|
#include <iostream>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
|
|
struct Node {
|
|
int x, y, height;
|
|
};
|
|
|
|
constexpr int MAX_N = 105;
|
|
constexpr short DX[4] = {0, 1, 0, -1}, DY[4] = {1, 0, -1, 0};
|
|
int r, c;
|
|
int heights[MAX_N][MAX_N];
|
|
vector<int> adj_nodes[MAX_N * MAX_N];
|
|
vector<Node> nodes;
|
|
|
|
int dp[MAX_N * MAX_N];
|
|
|
|
int pack_coord(int x, int y) {
|
|
return x * c + y;
|
|
}
|
|
|
|
int pack_coord(Node node) {
|
|
return pack_coord(node.x, node.y);
|
|
}
|
|
|
|
bool within_board(int x, int y) {
|
|
return 0 <= x && x < r && 0 <= y && y < c;
|
|
}
|
|
|
|
|
|
void log_dp() {
|
|
for (int i = 0; i < r * c; i++) {
|
|
clog << dp[i] << "\t";
|
|
if (i % c == c - 1) {
|
|
clog << endl;
|
|
}
|
|
}
|
|
}
|
|
|
|
void log_adj_nodes() {
|
|
for (int i = 0; i < r * c; i++) {
|
|
clog << i << " -> ";
|
|
for (int adj_node : adj_nodes[i]) {
|
|
clog << adj_node << " ";
|
|
}
|
|
clog << endl;
|
|
}
|
|
}
|
|
|
|
void init_adj_nodes() {
|
|
for (int i = 0; i < r; i++) {
|
|
for (int j = 0; j < c; j++) {
|
|
nodes.push_back({i, j, heights[i][j]});
|
|
int x = i, y = j;
|
|
for (int k = 0; k < 4; k++) {
|
|
int nx = x + DX[k], ny = y + DY[k];
|
|
if (within_board(nx, ny) && heights[nx][ny] > heights[x][y]) {
|
|
// 反向建图，小 -> 大
|
|
adj_nodes[pack_coord(x, y)].push_back(pack_coord(nx, ny));
|
|
}
|
|
}
|
|
}
|
|
}
|
|
sort(nodes.begin(), nodes.end(), [](const Node& a, const Node& b) {
|
|
return a.height > b.height;
|
|
});
|
|
}
|
|
|
|
|
|
void solve_dp() {
|
|
dp[pack_coord(nodes[0])] = 1;
|
|
for (int i = 1; i < nodes.size(); i++) {
|
|
Node curr_node = nodes[i];
|
|
int max_dp = 0;
|
|
for (int adj_node : adj_nodes[pack_coord(curr_node)]) {
|
|
max_dp = max(max_dp, dp[adj_node]);
|
|
}
|
|
dp[pack_coord(curr_node)] = max_dp + 1;
|
|
}
|
|
}
|
|
|
|
int get_ans() {
|
|
int max_dp = -1;
|
|
for (int i = 0; i < r * c; i++) {
|
|
max_dp = max(max_dp, dp[i]);
|
|
}
|
|
return max_dp;
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
cin >> r >> c;
|
|
for (int i = 0; i < r; i++) {
|
|
for (int j = 0; j < c; j++) {
|
|
cin >> heights[i][j];
|
|
}
|
|
}
|
|
|
|
init_adj_nodes();
|
|
solve_dp();
|
|
log_adj_nodes();
|
|
log_dp();
|
|
cout << get_ans() << endl;
|
|
|
|
return 0;
|
|
}
|