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 |
弱跑了900多MS,来教本叼优化啊#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[110][110],dp[110][110],vis[110][110]; int dir[4][2]={0,1,1,0,-1,0,0,-1}; void dfs(int x,int y) { int i,j,nx,ny; for(i=0;i<4;i++) { nx=x+dir[i][0]; ny=y+dir[i][1]; if(a[nx][ny]>a[x][y]&&!vis[nx][ny]&&a[x][y]!=-1&&dp[nx][ny]<dp[x][y]+1) { vis[nx][ny]=1; dp[nx][ny]=dp[x][y]+1; dfs(nx,ny); vis[nx][ny]=0; } } return; } int main() { int n,m,i,j; while(scanf("%d%d",&n,&m)==2) { int max=-1; memset(a,-1,sizeof(a)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&a[i][j]); } memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { vis[i][j]=1; dfs(i,j); vis[i][j]=0; for(int si=1;si<=n;si++) for(int sj=1;sj<=m;sj++) if(dp[si][sj]>max) { max=dp[si][sj]; // printf("%d %d\n",i,j); } //printf("%d ",max); } printf("%d\n",max+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