| ||||||||||
| 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