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

还是没有搞懂,为啥WA

Posted by suds at 2011-04-01 12:24:09 on Problem 1088
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Vertex
{
	int value;//the value of the vertex
	int outDegree;
	int inDegree;
	Vertex* conn[4];
	int   delta[4];
	bool bVisited;
	int maxpath;
	Vertex()
	{
		value = 0 ;
		outDegree = 0;
		inDegree = 0;
		bVisited = false;
		maxpath = 0;
		memset( conn , 0 , sizeof(conn) );
		memset( &delta , 0 , sizeof(delta) );
	}
};

struct PeakListNode 
{
	Vertex*	node;
	PeakListNode* next;
	PeakListNode()
	{
		node = NULL;
		next = NULL;
	}
};


Vertex* pHead = NULL;
Vertex* pVertexData = NULL;
PeakListNode* peakListHeader = NULL;

int direction[4][2]={{1,0},{0,1},{-1,0},{0,-1}};



void constructVertexList(int r,int c)
{
	static int dircount = sizeof(direction)/sizeof(direction[0]);

	for( int y = 0 ; y < r ; y++)	
	{
		for(int x = 0 ; x < c ; x++ )
		{
			Vertex* pCur = &pVertexData[ c * y+ x ];
			for( int i = 0; i < dircount ; i++)
			{
				int cx = x + direction[i][0];
				int cy = y + direction[i][1];
				if( cx < 0 || cx >= c || cy < 0 || cy >= r )
					continue;				
				
				Vertex* pNext = &pVertexData[ c * cy + cx ];
				if(pCur->value > pNext->value)
				{
					pCur->conn[ pCur->outDegree++ ] = pNext;
				}
				else
				{
					pCur->inDegree++;
				}
			}
			if(pCur->inDegree<=0)
			{//this vertex should be a peak
				PeakListNode* pPeakNode =  new PeakListNode();
				pPeakNode->node = pCur;
				if( NULL == peakListHeader )
				{
					peakListHeader = pPeakNode;
				}
				else
				{
					pPeakNode->next = peakListHeader;
					peakListHeader = pPeakNode; 
				}
			}
		}
	}
}

int findWaydown(Vertex* p)
{
	if( p->bVisited )
		return p->maxpath;

	p->bVisited = true;
	int maxpath = 0;
	for( int i = 0 ;i < p->outDegree ; i++ )
	{
		int pathlen = findWaydown( p->conn[i] );
		if( pathlen > maxpath )
		{
			maxpath = pathlen;
		}
	}
	p->maxpath = maxpath + 1;
	return p->maxpath;
}

int findmaxlenpath()
{
	int maxpaths = 0;
	PeakListNode* p = peakListHeader;
	while( p )
	{
		int pathlen = findWaydown(p->node);
		p=p->next;
		if( pathlen > maxpaths )
			maxpaths = pathlen;
	}
	return maxpaths;
}

int main()
{
	int r = 0 , c = 0 ;
	scanf("%d %d",&r,&c);
	pVertexData = new Vertex[r*c];	
	for( int i = 0 ; i < r*c;i++ )
	{//get all data
		int data;
		scanf("%d",&data);
		pVertexData[i].value = data;
	}
	constructVertexList(r,c);
	int maxpath = findmaxlenpath();
	printf("%d\n",maxpath);
	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