| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
坑爹啊,高度相等不行,否则re.另付代码#include<iostream>
using namespace std;
#define MAX 105
#define max(a, b) ((a) > (b) ? (a) : (b))
#define inf 1000000000
int map[MAX][MAX];//MAP
int dp[MAX][MAX];//dp[i][j]:到(i, j)距离最大值
int vist[MAX][MAX];
int r, c;//R, C
int solve(int x, int y)
{
if(x >= r || y >= c) return 0;
if(vist[x][y] != 0) return dp[x][y];
int ans = 0;
if(x - 1 >= 0 && map[x][y] < map[x - 1][y]) ans = max(ans, solve(x - 1, y) + 1);
if(x + 1 < r && map[x][y] < map[x + 1][y]) ans = max(ans, solve(x + 1, y) + 1);
if(y - 1 >= 0 && map[x][y] < map[x][y - 1]) ans = max(ans, solve(x, y - 1) + 1);
if(y + 1 < c && map[x][y] < map[x][y + 1]) ans = max(ans, solve(x, y + 1) + 1);
vist[x][y] = 1;//标记已访问
dp[x][y] = max(ans, dp[x][y]);
return dp[x][y];
}
int main()
{
int i, j;
//freopen("out.txt", "w", stdout);
//freopen("in.txt", "r", stdin);
while(scanf("%d%d", &r, &c) != EOF)
{
for(i = 0; i < r; i ++)//row
{
for(j = 0; j < c; j ++) //col
{
scanf("%d", &map[i][j]);
dp[i][j] = 1;
}
}
//dp
int ans = 0;
memset(vist, 0, sizeof(vist));
for(i = 0; i < r; i ++)
{
for(j = 0; j < c; j ++)
{
solve(i, j);
ans = max(dp[i][j], ans);
}
}
printf("%d\n", ans);
}
}
/*
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
4 4
1478 9358 6962 4464
5705 8145 3281 6827
9961 491 2995 1942
4827 5436 2391 4604
25 5
*/
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator