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 |
大家瞧瞧我的代码,第一次dfs通过。接着我优化下,结果既然错了。测试无数次都可以啊。。*****************************错误的。。 #include <iostream> #include <cstdlib> using namespace std; int m,n; int t[101][101]={0},v[101][101]={0}; struct Node { int x; int y; int v; }; struct Node ALL[201*201]; int cmp(const void *a,const void* b) { struct Node N1=*(struct Node *)a; struct Node N2=*(struct Node *)b; return N1.v-N2.v; } int dfs(int a,int b) { int temp=0; if(a-1>=0 && t[a][b]>t[a-1][b]) //选择向下 { if( v[a-1][b]==0 ) { v[a-1][b]=dfs(a-1,b); } if(temp<v[a-1][b])temp=v[a-1][b]; } if(a+1<m && t[a][b]>t[a+1][b]) { if (v[a+1][b]==0) { v[a+1][b]=dfs(a+1,b); } if(temp<v[a+1][b])temp=v[a+1][b]; } if(b-1>=0 && t[a][b]>t[a][b-1]) { if( v[a][b-1]==0) { v[a][b-1]=dfs(a,b-1); } if(temp<v[a][b-1])temp=v[a][b-1]; } if(b+1<n && t[a][b]>t[a][b+1]) { if( v[a][b+1]==0) { v[a][b+1]=dfs(a,b+1); } if(temp<v[a][b+1])temp=v[a][b+1]; } v[a][b]=1+temp; return v[a][b]; } int main() { cin>>m>>n; int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) { scanf("%d",&t[i][j]); ALL[ i*m+j ].x=i; ALL[ i*m+j ].y=j; ALL[ i*m+j ].v=t[i][j]; } qsort(ALL,m*n,sizeof(ALL[0]),cmp); int max=0; for( i=0;i<m*n; i++) { if(max< dfs(ALL[i].x,ALL[i].y) ) { max=v[ ALL[i].x ][ ALL[i].y ]; } } /* ouput all data for(i=0;i<m*n;i++) cout<<ALL[i].x<<' '<<ALL[i].y<<' '<<ALL[i].v<<endl; */ /* for(i=0;i<m;i++) for(j=0;j<n;j++) { if(max<v[i][j]) { max=v[i][j]; } } */ cout<<max<<endl; system("pause"); return 0; } *****************AC的代码 #include <iostream> using namespace std; int m,n; int t[101][101]={0},v[101][101]={0}; int dfs(int a,int b) { int temp=0; if(a-1>=0 && t[a][b]>t[a-1][b]) //选择向下 { if( v[a-1][b]==0 ) { v[a-1][b]=dfs(a-1,b); } if(temp<v[a-1][b])temp=v[a-1][b]; } if(a+1<m && t[a][b]>t[a+1][b]) { if (v[a+1][b]==0) { v[a+1][b]=dfs(a+1,b); } if(temp<v[a+1][b])temp=v[a+1][b]; } if(b-1>=0 && t[a][b]>t[a][b-1]) { if( v[a][b-1]==0) { v[a][b-1]=dfs(a,b-1); } if(temp<v[a][b-1])temp=v[a][b-1]; } if(b+1<n && t[a][b]>t[a][b+1]) { if( v[a][b+1]==0) { v[a][b+1]=dfs(a,b+1); } if(temp<v[a][b+1])temp=v[a][b+1]; } v[a][b]=1+temp; return v[a][b]; } int main() { cin>>m>>n; int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) scanf("%d",&t[i][j]); int max=0; for(i=0;i<m;i++) for(j=0;j<n;j++) { if(max<dfs(i,j)) { max=v[i][j]; } } cout<<max<<endl; // system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator