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