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

弱跑了900多MS,来教本叼优化啊

Posted by shit at 2015-06-10 21:29:52 on Problem 1088
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[110][110],dp[110][110],vis[110][110];
int dir[4][2]={0,1,1,0,-1,0,0,-1};
void dfs(int x,int y)
{
	int i,j,nx,ny;
	for(i=0;i<4;i++)
	{
		nx=x+dir[i][0];
		ny=y+dir[i][1];
		if(a[nx][ny]>a[x][y]&&!vis[nx][ny]&&a[x][y]!=-1&&dp[nx][ny]<dp[x][y]+1)
		{
			vis[nx][ny]=1;
			dp[nx][ny]=dp[x][y]+1;
			dfs(nx,ny);
			vis[nx][ny]=0;
		}
	}
	return;
}			
int main()
{
	int n,m,i,j;
	while(scanf("%d%d",&n,&m)==2)
	{
		int max=-1;
		memset(a,-1,sizeof(a));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&a[i][j]);
			}
		memset(dp,0,sizeof(dp));
		memset(vis,0,sizeof(vis));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				vis[i][j]=1;
				dfs(i,j);
				vis[i][j]=0;
				for(int si=1;si<=n;si++)
					for(int sj=1;sj<=m;sj++)
						if(dp[si][sj]>max)
						{
							max=dp[si][sj];
						//	printf("%d %d\n",i,j);
						}
				//printf("%d ",max);
			}
		printf("%d\n",max+1);
	}
	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