这个题我觉得自己写的程序可以得到正确的结果啊，可结果是Wrong Answer。可以帮俺
看看有什么没考虑周全么？谢谢。另外，如果我做的程序即超时又错误，那么会被判作
什么？即Time Limit Exceed和Wrong Answer哪个优先级更高？

滑雪

Time Limit:1000MS  Memory Limit:65536K
Total Submit:2517 Accepted:612 

Description 
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域
必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。
Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代
表点的高度。下面是一个例子 


 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

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子
中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最
长的一条。

Input 
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整
数，代表高度h，0<=h<=10000。

Output 
输出最长区域的长度。

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

Source 
Don't know

程序：
#include <iostream>
using namespace std;

//define the level status of link
#define HIGH 1
#define EDGE 0
#define LOW  -1
#define DIMENSION 100

int nColNum, nRowNum;
int Area[DIMENSION][DIMENSION];

typedef struct _LinkStatus
{
	int nLeft;
	int nTop;
	int nRight;
	int nBottom;
} LinkStatus;

LinkStatus status[DIMENSION][DIMENSION];

void InitLinkStatus()
{
	int i, j;
	int xTail = nColNum - 1;
	int yTail = nRowNum - 1;
	///////////////////////////////////////////////////////////////////
///////
	// initialize four edges
	for(i = 0; i < nRowNum; i++)
	{	// initialize the left line
		status[0][i].nLeft = EDGE;
	}

	for(i = 0; i < nColNum; i++)
	{	// initialize the top line
		status[i][0].nTop = EDGE;
	}

	for(i = 0; i < nRowNum; i++)
	{	// initialize the right line
		status[xTail][i].nRight = EDGE;
	}

	for(i = 0; i < nColNum; i++)
	{	// initialize the bottom line
		status[i][yTail].nBottom = EDGE;
	}

	///////////////////////////////////////////////////////////////////
///////
	// initialize horizontally
	for(i = 0; i < nRowNum; i++)
	{
		for(j = 0; j < xTail; j++)
		{
			if(Area[j][i] > Area[j + 1][i])
			{
				status[j][i].nRight = HIGH;
				status[j + 1][i].nLeft = LOW;
			}
			else if(Area[j][i] < Area[j + 1][i])
			{
				status[j][i].nRight = LOW;
				status[j + 1][i].nLeft = HIGH;
			}
			else
			{
				status[j][i].nRight = LOW;
				status[j + 1][i].nLeft = LOW;
			}
		}
	}

	///////////////////////////////////////////////////////////////////
///////
	// initialize vertically
	for(j = 0; j < nColNum; j++)
	{
		for(i = 0; i < xTail; i++)
		{
			if(Area[j][i] > Area[j][i + 1])
			{
				status[j][i].nBottom = HIGH;
				status[j][i + 1].nTop = LOW;
			}
			else if(Area[j][i] < Area[j][i + 1])
			{
				status[j][i].nBottom = LOW;
				status[j][i + 1].nTop = HIGH;
			}
			else
			{
				status[j][i].nBottom = LOW;
				status[j][i + 1].nTop = LOW;
			}
		}
	}
}

// return the longest path starting from the area(x, y)
int GetLongestPath(int x, int y)
{
	int nMax, nTemp;
	nMax = 0;
	//test each path
	if(status[x][y].nLeft == HIGH)
	{
		nTemp = GetLongestPath(x - 1, y);
		if(nMax < nTemp)
		{
			nMax = nTemp;
		}
	}

	if(status[x][y].nTop == HIGH)
	{
		nTemp = GetLongestPath(x, y - 1);
		if(nMax < nTemp)
		{
			nMax = nTemp;
		}
	}

	if(status[x][y].nRight == HIGH)
	{
		nTemp = GetLongestPath(x + 1, y);
		if(nMax < nTemp)
		{
			nMax = nTemp;
		}
	}

	if(status[x][y].nBottom == HIGH)
	{
		nTemp = GetLongestPath(x, y + 1);
		if(nMax < nTemp)
		{
			nMax = nTemp;
		}
	}
	// if the current point is a valley, nMax keeps 0
	return nMax + 1;
}
int main()
{
	int i, j, nMax, nTemp;

	//load the input information
	cin>>nRowNum>>nColNum;
	for(i = 0; i < nRowNum; i++)
		for(j = 0; j < nColNum; j++)
			cin>>Area[j][i];
	
	InitLinkStatus();
	
	nMax = 1;
	for(i = 0; i < nRowNum; i++)
	{
		for(j = 0; j < nColNum; j++)
		{
			//only a peak needs to trace as the start 
point
			if((status[j][i].nLeft > LOW) &&
			   (status[j][i].nTop  > LOW) &&
			   (status[j][i].nRight > LOW) &&
			   (status[j][i].nBottom > LOW))
			{
				nTemp = GetLongestPath(j, i);
				if(nMax < nTemp)
				{
					nMax = nTemp;
				}
			}
		}
	}

	//output the result
	cout<<nMax<<endl;
	return 0;
}

• peak可能在边界上 (4662) c0500448242 2005-08-13 11:40:37
  • Re:peak可能在边界上 (151) speedfirst 2005-08-13 11:51:57
  • 我觉得我已经考虑到这个问题了啊 (154) speedfirst 2005-08-13 11:53:16
    • 发现你把yTail打成xTail了 (172) c0500448242 2005-08-13 12:19:42
      • 嗯，的确是它的问题。现在结果改成TLE了。TLE的意思是结果对了，只是超时么？ (83) speedfirst 2005-08-13 12:43:07
        • 你这个程序复杂度是指数级的,而且显然深搜的那一块用了绝大部分时间,想怎么优化吧 (112) c0500448242 2005-08-13 12:45:35
    • 还有一个问题刚才忘了说:高度相同的话,是不能够滑过去的 (21) c0500448242 2005-08-13 12:51:03
      • 这个我似乎也考虑到了啊 (111) speedfirst 2005-08-13 12:59:29
• 才发现这个题的算法复杂度是O(n^2)的 (4662) c0500448242 2005-08-13 12:41:20
  • 难到可以改成nlogn的？如果能我努力试试改改。 (46) speedfirst 2005-08-13 12:45:47
    • 我说的是AC的代码大部分是n^2:),你的还不是 (52) c0500448242 2005-08-13 12:46:47
      • 再加三行就n^2了 (0) T3 2005-08-13 12:52:23
        • ... (0) c0500448242 2005-08-13 12:52:39
        • 有什么优化的建议么？ (0) speedfirst 2005-08-13 12:55:44