Cod sursa(job #1010226)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 14 octombrie 2013 16:07:06
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#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;
}