# 11063: 【原1063】小M爱滑雪

### 题目描述

author: duruofei 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1063

## Description

1  2  3  4  5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9


## Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9


## Sample Output

25


## Hint

70%的数据 $$1 \leq R,C \leq 100$$

100%的数据 $$1 \leq R,C \leq 500$$

## FineArtz's solution

/* 小M爱滑雪 */
#include <iostream>
using namespace std;

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

int a[505][505], f[505][505] = {0};
int r, c;

int search(int x, int y){
if (f[x][y] != 0)
return f[x][y];
int t[4] = {0};
for (int i = 0; i < 4; ++i){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 1 && ny >= 1 && nx <= r && ny <= c)
if (a[x][y] > a[nx][ny])
t[i] = 1 + search(nx, ny);
}
int ret = 1;
for (int i = 0; i < 4; ++i)
if (ret < t[i])
ret = t[i];
f[x][y] = ret;
return ret;
}

int main(){
cin >> r >> c;
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j)
cin >> a[i][j];
int ans = 0;
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j)
ans = max(ans, search(i, j));
cout << ans << endl;
return 0;
}


## yyong119's solution

#include <cstdio>
#include <iostream>

using namespace std;

const int movement[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int data[501][501], f[501][501];
int n, m, longest;

int dfs(int x, int y) {

int nx, ny, maxx = 0;

if (f[x][y]) return f[x][y];
for (int i = 0; i <= 3; i++) {
nx = x + movement[i][0];
ny = y + movement[i][1];
if ((nx > 0) && (ny > 0) && (nx <= n) && (ny <= m) && (data[nx][ny] < data[x][y]))
maxx = max(maxx, dfs(nx, ny));
}
f[x][y] = maxx + 1;
return f[x][y];
}

int main() {

scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) scanf("%d", &data[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
f[i][j] = dfs(i, j);
longest = max(longest, f[i][j]);
}
printf("%d\n", longest);
return 0;
}