| ||||||||||
| 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 | |||||||||
小白记忆话搜索练习开始以为广搜一下就可一乐,后来发现自己太naive了。。。
优化后的代码,大神轻喷。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
int arr[105][105];
int dp[105][105]={-1};
int n,m;
int mx(int a,int b,int c,int d)
{
int temp=0;
if(a>temp)
temp=a;
if(b>temp)
temp=b;
if(c>temp)
temp=c;
if(d>temp)
temp=d;
return temp;
}
int res(int x,int y)
{
int a=0,b=0,c=0,d=0;
if(dp[x][y]>0)
return dp[x][y];
if(x>n||x<=0||y<=0||y>m)
return 0;
else if(arr[x-1][y]>=arr[x][y]&&arr[x+1][y]>=arr[x][y]&&arr[x][y-1]>=arr[x][y]&&arr[x][y+1]>=arr[x][y])
return dp[x][y]=0;
else
{
if(arr[x+1][y]<arr[x][y])
a=res(x+1,y);
if(arr[x-1][y]<arr[x][y])
b=res(x-1,y);
if(arr[x][y+1]<arr[x][y])
c=res(x,y+1);
if(arr[x][y-1]<arr[x][y])
d=res(x,y-1);
}
return dp[x][y]=mx(a,b,c,d)+1;
}
int main(void)
{
while(scanf("%d%d",&n,&m)==2)
{
memset(dp,0,sizeof(dp));
memset(arr,0x3f,sizeof(arr));
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++j)
scanf("%d",&arr[i][j]);
}
int mn=-99;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++j)
{
int temp=res(i,j);
mn=max(mn,temp);
}
}
printf("%d\n",mn+1);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator