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

超时,如何优化?(代码如下:)

Posted by abcvisa at 2006-07-22 17:40:52 on Problem 1088
#include<iostream>

using namespace std;

typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *nextarc;
	int data;
}ArcNode;

typedef struct VNode
{
	int data;
	int flag;
	ArcNode *firstarc;
}VNode;


int i,j,r,c,a[100][100],w,k,nextstep[4][2]={0,1,0,-1,1,0,-1,0};
int nexti,nextj;
VNode L[10000];
ArcNode *p;
		
void  DFS(VNode L[10000], int v, int &sum, int t)
{
	ArcNode *p;
	if(sum<t) sum=t;
	for(p=L[v].firstarc; p ; p=p->nextarc)
	{
		w=p->adjvex;
		if(L[w].flag)
			DFS(L,w,sum,t+1);
	}

}

int  main()
{


	cin>>r>>c;

	for(i=0; i<r; i++)
		for(j=0; j<c; j++)
		{
			cin>>a[i][j];
			L[i*c+j].data = a[i][j];
			L[i*c+j].flag=1;
			L[i*c+j].firstarc=NULL;
		}
	for(i=0; i<r; i++)
		for(j=0; j<c; j++)
			for(k=0; k<4; k++)
			{
				nexti=nextstep[k][0]+i;
				nextj=nextstep[k][1]+j;
				if(  nexti>=0 && nexti<r && nextj>=0 && nextj<c  && a[nexti][nextj]>a[i][j] )
				{
	
					p=new ArcNode;
					p->adjvex= nexti*c + nextj;
					p->data = a[nexti][nextj];
					p->nextarc=L[i*c+j].firstarc;
					L[i*c+j].firstarc=p;
				}

			}

	int max=0,count,t;
	for(i=0; i<r*c-1; i++)
	{
		t=count=1;
		if(L[i].flag)
			DFS(L,i,count,t);
		if(max<count) max=count;
	}
	cout<<max<<endl;

	return 1;

}




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