Pagini recente » Istoria paginii runda/con | Cod sursa (job #170717) | Cod sursa (job #1686972) | Cod sursa (job #2104479) | Cod sursa (job #1010226)
#include <fstream>
using namespace std;
ifstream f("alpin.in");
ofstream g("alpin.out");
#define Nmax 1030
int a[Nmax][Nmax], b[Nmax][Nmax],n;
int dl[]={0,1,0,-1};
int dc[]={1,0,-1,0};
int dfs(int l,int c)
{
if(b[l][c]) return b[l][c];
else
{ int v;b[l][c]=1;
for(int i=0;i<4;++i)
{
int lcur,ccur;
lcur=l+dl[i];ccur=c+dc[i];
if(a[l][c]<a[lcur][ccur])
{
v=dfs(lcur,ccur);
if(v+1>b[l][c])
b[l][c]=v+1;
}
}
return b[l][c];
}
}
void afisare(int l, int c)
{
g<<l<<' '<<c<<'\n';
while(b[l][c]>1){
for(int i=0;i<4; ++i)
{
int lc=l+dl[i],cc=c+dc[i];
if(b[l][c]-1==b[lc][cc] && a[l][c]<a[lc][cc])
{
l=lc,c=cc;
g<<l<<' '<<c<<'\n';
break;
}
}
}
}
int main()
{
f>>n;
int i,j,col=1,lin=1,Lmax=0;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
f>>a[i][j];
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
b[i][j]=dfs(i,j);
if(b[i][j]>Lmax)
{
Lmax=b[i][j],lin=i,col=j;
}
}
g<<Lmax<<'\n';
afisare(lin,col);
return 0;
}