| ||||||||||
| 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 | |||||||||
还是没有搞懂,为啥WA#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator