AidenHou @ 2022-12-28 19:21:09
我的提交记录 链接 代码如下:
#include <iostream>
#include <cmath>
//#include <cstring>
//#include <cstdio>
#include <algorithm>
#include <vector>
//#include <numeric>
//#define UC unsigned char
//#define US unsigned short
//#define U unsigned int
//#define ULL unsigned long long
//#define DEBUG
struct Point {
int r, c, value;
};
bool compare(Point a, Point b)
{
return a.value < b.value;
}
int main()
{
using namespace std;
int r, c;
cin >> r >> c;
vector<Point> points(r * c, Point());
int** dp = new int*[r];
points.shrink_to_fit();
for (int i = 0; i < r; i++)
{
dp[i] = new int[c];
for (int j = 0; j < c; j++)
{
dp[i][j] = -1;
cin >> points[i * c + j].value;
points[i * c + j].r = i;
points[i * c + j].c = j;
}
}
// printf("%d %d %d\n", points[5].r, points[5].c, points[5].value);
sort(points.begin(), points.end(), compare);
// printf("%d %d %d\n", points[r * c - 1].r, points[r * c - 1].c, points[r * c - 1].value);
// printf("%d\n", points[0].value);
int up, down, left, right, cr, cc, cmax = -1;
for (int i = 0; i < r * c; i++)
{
cr = points[i].r;
cc = points[i].c;
up = cr > 0 ? dp[cr - 1][cc] : -1;
down = cr < r - 1 ? dp[cr + 1][cc] : -1;
left = cc > 0 ? dp[cr][cc - 1] : -1;
right = cc < c - 1 ? dp[cr][cc + 1] : -1;
dp[cr][cc] = max(
0, max(
up, max(
down, max(
left,
right)))
) + 1;
cmax = max(cmax, dp[cr][cc]);
}
cout << cmax << endl;
return 0;
}