Pagini recente » Cod sursa (job #2667051) | Cod sursa (job #2065335) | Cod sursa (job #2209749) | Cod sursa (job #2535185) | Cod sursa (job #1121715)
#include <fstream>
#include <queue>
#include <string.h>
using namespace std;
fstream f("alpin.in",ios::in);
fstream g("alpin.out",ios::out);
const int nmax=1030;
int n,i,j,x,y,maxim,nrs,solx[nmax*nmax],soly[nmax*nmax],a[nmax][nmax],d[nmax][nmax],px[nmax][nmax],py[nmax][nmax];
void citire()
{
f>>n;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) f>>a[i][j];
}
void constr(int x,int y)
{
solx[nrs]=x;soly[nrs]=y;
nrs--;
if (nrs>0) constr(px[x][y],py[x][y]);
}
void parcurgere()
{
queue <int> lin;
queue <int> col;
queue <int> dist;
lin.push(x);
col.push(y);
dist.push(1);
int sch=0,di,xm=0,ym=0;
while (!lin.empty())
{
x=lin.front();
y=col.front();
di=dist.front();
lin.pop();col.pop();dist.pop();
d[x][y]=di;
if (di>maxim)
{
maxim=di;
xm=x;ym=y;
sch=1;
}
if ((x>1)&&(a[x-1][y]>a[x][y])&&(d[x-1][y]<di+1))
{
dist.push(di+1);
lin.push(x-1);col.push(y);
px[x-1][y]=x;
py[x-1][y]=y;
}
if ((x<n)&&(a[x+1][y]>a[x][y])&&(d[x+1][y]<di+1))
{
dist.push(di+1);
lin.push(x+1);col.push(y);
px[x+1][y]=x;
py[x+1][y]=y;
}
if ((y>1)&&(a[x][y-1]>a[x][y])&&(d[x][y-1]<di+1))
{
dist.push(di+1);
lin.push(x);col.push(y-1);
px[x][y-1]=x;
py[x][y-1]=y;
}
if ((y<n)&&(a[x][y+1]>a[x][y])&&(d[x][y+1]<di+1))
{
dist.push(di+1);
lin.push(x);col.push(y+1);
px[x][y+1]=x;
py[x][y+1]=y;
}
}
if (sch)
{
nrs=maxim;
memset(solx,0,sizeof(solx));
memset(soly,0,sizeof(soly));
constr(xm,ym);
}
}
int main()
{
citire();
maxim=0;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) if (!d[i][j]) {
x=i;y=j;
parcurgere();
}
g<<maxim<<'\n';
for (i=1;i<=maxim;i++) g<<solx[i]<<" "<<soly[i]<<'\n';
f.close();g.close();
return 0;
}