洛谷 P1434 滑雪
记忆化搜索,每个位置都往下搜,搜索到最低点,然后可以依次计算路径上每个点的高度。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int depth(vector<vector<int>>& area, vector<vector<int>>& f, int i, int j) {
if (f[i][j]) return f[i][j];
int m = area.size() - 1, n = area[0].size() - 1;
int u = (i > 0 && area[i-1][j] < area[i][j]) ? depth(area, f, i-1, j) + 1 : 0;
int d = (i < m && area[i+1][j] < area[i][j]) ? depth(area, f, i+1, j) + 1 : 0;
int l = (j > 0 && area[i][j-1] < area[i][j]) ? depth(area, f, i, j-1) + 1 : 0;
int r = (j < n && area[i][j+1] < area[i][j]) ? depth(area, f, i, j+1) + 1 : 0;
f[i][j] = max({u, d, l ,r});
return f[i][j];
}
int main(int argc, char* argv[]) {
int r, c;
scanf("%d %d", &r, &c);
vector<vector<int>> area(r, vector<int>(c, 0));
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
scanf("%d", &area[i][j]);
}
}
int ans = 0;
vector<vector<int>> f(r, vector<int>(c, 0));
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
if (!f[i][j]) ans = max(ans, depth(area, f, i, j) + 1);
}
}
printf("%d\n", ans);
return 0;
}
Comments