| ||||||||||
| 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 | |||||||||
我的递归解法,是超时的.高手指点一点算法的优化#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator