Cod sursa(job #1121715)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 25 februarie 2014 13:47:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#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;
}