Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

坑爹啊,高度相等不行,否则re.另付代码

Posted by 058179 at 2013-10-07 16:13:46 on Problem 1088
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator