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 ths at 2007-05-24 15:12:08 on Problem 1088
#include<iostream.h>


int r,c;
void count(int i,int j,int &result,int total,int **p,bool ** flag)
{
	int m=p[i][j];	
	//比周围的小或周围是边界
	if(((total+m)>=result)&&(i+1>=r||p[i+1][j]>m)&&(i-1<0||p[i-1][j]>m)&&(j-1<0||p[i][j-1]>m)&&(j+1>=c||p[i][j+1]>m))
    {
		total+=m;
		result=total;
		return;
	}
    //上下左右搜索
	if(i+1<r&&p[i+1][j]<m&&!flag[i+1][j])
	{
		flag[i+1][j]=true;
        count(i+1,j,result,total+m-p[i+1][j],p,flag);
		flag[i+1][j]=false;
	}
	if(i-1>=0&&p[i-1][j]<m&&!flag[i-1][j])
	{
		flag[i-1][j]=true;
        count(i-1,j,result,total+m-p[i-1][j],p,flag);
		flag[i-1][j]=false;
	}
	if(j+1<c&&p[i][j+1]<m&&!flag[i][j+1])
	{
		flag[i][j+1]=true;
        count(i,j+1,result,total+m-p[i][j+1],p,flag);
		flag[i][j+1]=false;
	}
	if(j-1>=0&&p[i][j-1]<m&&!flag[i][j-1])
	{
		flag[i][j-1]=true;
        count(i,j-1,result,total+m-p[i][j-1],p,flag);
		flag[i][j-1]=false;
	}
}

int main()
{
	
	int i,j,m,n;
	int result=0,temp=0;
	cin>>r>>c;
	int **p=new int *[r];
	bool **flag=new bool *[r];
	for(i=0;i<r;i++)
	{
		flag[i]=new bool [c];
		p[i]=new int [c];
		for(j=0;j<c;j++)
		cin>>p[i][j];
	}
    
	
	for(i=0;i<r;i++)
	{
		for(j=0;j<c;j++)
		{	
			temp=0;
			for(m=0;m<r;m++)
			for(n=0;n<c;n++)
			{
		         flag[m][n]=false;
			}
			flag[i][j]=true;
			count(i,j,temp,0,p,flag);		
			if(temp>result) result=temp;
		}
	}
    cout<<result<<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