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:感觉上好像不用递归会更快,62ms,一会去试试,哪位大牛提供更好的方法

Posted by tq010or at 2007-11-13 18:25:43 on Problem 1088
In Reply To:感觉上好像不用递归会更快,62ms,一会去试试,哪位大牛提供更好的方法 Posted by:zbleach at 2006-10-08 12:08:20
请问你程序中的Flags数组是做什么用的?
> #include <iostream>
> using namespace std;
> 
> //算法比较简明,就是搜索加数据存储
> 
> bool flags[100][100];
> int max[100][100];
> int elements[100][100];
> int m, n;
> 
> int maxlength(int i, int j)
> {
> 	if(max[i][j] >= 0)
> 		return max[i][j];
> 	int temp[4] = {0};
> 	if(i > 0 && elements[i][j] > elements[i - 1][j])
> 	{
> 		temp[0] = maxlength(i - 1, j) + 1;
> 		flags[i - 1][j] = false;
> 	}
> 	if(j > 0 && elements[i][j] > elements[i][j - 1])
> 	{
> 		temp[1] = maxlength(i, j - 1) + 1;
> 		flags[i][j - 1] = false;
> 	}
> 	if(j < n - 1 && elements[i][j] > elements[i][j + 1])
> 	{
> 		temp[2] = maxlength(i, j + 1) + 1;
> 		flags[i][j + 1] = false;
> 	}
> 	if(i < m - 1 && elements[i][j] > elements[i + 1][j])
> 	{
> 		temp[3] = maxlength(i + 1, j) + 1;
> 		flags[i + 1][j] = false;
> 	}
> 	int result = temp[0];
> 	for(int k = 1; k < 4; ++ k)
> 		if(result < temp[k])
> 			result = temp[k];
> 	max[i][j] = result;
> 	return result;
> }
> 
> int main()
> {
> 	int i;
> 	cin >> m >> n;
> 	for(i = 0; i < m; ++ i)
> 		for(int j = 0; j  < n; ++ j)
> 		{
> 			cin >> elements[i][j];
> 			max[i][j] = -1;
> 			flags[i][j] = true;
> 		}
> 	int nmax = 0;
> 	for(i = 0; i < m; ++ i)
> 		for(int j = 0; j < n; ++ j)
> 			if(flags[i][j])
> 			{
> 				maxlength(i, j);
> 				if(nmax < max[i][j])
> 					nmax = max[i][j];
> 			}
> 	cout << nmax + 1 << endl;
> 	return 0;
> }

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