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

Re:求助:算法没问题啊 怎么会超时啊 贴出代码

Posted by sunzuhan at 2010-08-15 14:20:10 on Problem 1088
In Reply To:求助:算法没问题啊 怎么会超时啊 贴出代码 Posted by:solopointer at 2010-08-08 20:57:42
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 101
int map[N][N];
int used[N][N];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int r,c;
int dfs(int x,int y)
{
	int maxs=0,h,i;
	int tx,ty;
	if(used[x][y]!=-1)
	return used[x][y];
	
	h=map[x][y];
	
	for(i=0;i<4;i++)
	{
		tx=x+dir[i][0];
		ty=y+dir[i][1];
	    if(tx>=1 && tx<=r && ty>=1 && ty<=c && h>map[tx][ty])
	    {
	      if(maxs<dfs(tx,ty)+1)
	      maxs=dfs(tx,ty)+1;
	    }
	}
	
	return used[x][y]=maxs;
}
int main()
{
	int maxs=0;
	int i,j; 
	cin>>r>>c;
	for(i=1;i<=r;i++)
	for(j=1;j<=c;j++)
	{
	cin>>map[i][j];
	used[i][j]=-1;
	}
	
	for(i=1;i<=r;i++)
	for(j=1;j<=c;j++)
	if(maxs<dfs(i,j))
	maxs=dfs(i,j);
	
	cout<<maxs+1<<endl;
	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