| ||||||||||
| 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:感觉上好像不用递归会更快,62ms,一会去试试,哪位大牛提供更好的方法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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator