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