POJ1088 滑雪(记忆化搜索)

时间:2021-08-15 21:38:19

题目链接

分析:

状态转移方程 d[i][j] = max(d[i-1][j], d[i+1][j], d[i][j-1], d[i][j+1])。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cmath> using namespace std; const int maxn = +; int a[maxn][maxn], d[maxn][maxn], n, m; int dx[] = {, , -, };
int dy[] = {-, , , }; int dfs(int x, int y) {
if(d[x][y] > ) return d[x][y]; int ans = ;
int nx, ny; for(int i=; i<; i++) {
nx = x+dx[i];
ny = y+dy[i]; if(nx >= && nx < n && ny >= && ny < m && a[x][y] > a[nx][ny]) {
ans = max(ans, dfs(nx, ny));
}
} return d[x][y] = ans+;
} int main() {
// freopen("my.txt", "r", stdin); while(scanf("%d%d", &n, &m) == ) {
for(int i=; i<n; i++) {
for(int j=; j<m; j++) {
scanf("%d", &a[i][j]);
}
} memset(d, -, sizeof(d)); int ans = -;
for(int i=; i<n; i++) {
for(int j=; j<m; j++) {
if(d[i][j] == -) ans = max(ans, dfs(i, j));
}
} printf("%d\n", ans);
} return ;
}