infoarena

5
1 2 3 4 5
10 9 8 7 6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25

25
1 1
1 2
1 3
1 4
1 5
2 5
2 4
2 3
2 2
2 1
3 1
3 2
3 3
3 4
3 5
4 5
4 4
4 3
4 2
4 1
5 1
5 2
5 3
5 4
5 5

pentru h de la 1 la ALTITUDINE_MAXIMA
          pentru toate casutele (i j) cu altitudinea h
                    M[i][j] = maxim(M[sx][sy]) + 1, (sx sy) vecin cu (i j) si altitudinea din (sx sy) < altitudinea din (i j)

function f(int i, int j)
{
    daca best[i][j] > 0, returneaza best[i][j];

    ptr cei 4 vecini ai lui (i, j)
        daca Inaltime(vecin) < Inaltime( (i, j) ) si f(vecin) > best[i][j]
             best[i][j] = f(vecin);
    best[i][j] += 1;

    returneaza best[i][j];
}

5
1 3
1 4
2 4
3 4
4 4

...
char buffer[NMAX * 6 + 1], tmp;
gets(buffer);
for( i = 0, nr = 0; i < n; ++i )
    {
    sscanf(buffer, "%c", &tmp);
    if( tmp == ' ')
        ++nr;
    else
        a[nr] = a[nr] * 10 + tmp - '0';
    }

if( ii>=1 && jj>=1 && ii<=n && jj<=n &&  a[i][j] < a[ii][jj] ) {
	d[ii][jj]=d[i][j]+1;
	Q.push(mp(ii,jj));
}

5
1 3
1 4
2 4
3 4
4 4

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("alpin.in");
ofstream fout("alpin.out");

int n;
int alt[1025][1025];
int sol[1025][1025];
bool ok=1;

int rezi[1025],rezj[1025];
int maxim=0;
int pozi,pozj;

struct P
{
    P(){};
    P(int _x,int _y)
    {
        x=_x;
        y=_y;
    }
    int x,y;
    int alt;
} poz[1025*1025];

void bkt(int val,int i,int j);

vector<vector<P> >S;

int main()
{
    int i,j,k=0;

    fin>>n;

    S.resize(16385);

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fin>>alt[i][j];
            S[alt[i][j]].push_back(P(j,i));
        }

    for(i=1;i<S.size();i++)
        for(j=0;j<S[i].size();j++)
        {
            poz[k]=S[i][j];
            poz[k++].alt=i;
        }

    for(i=0;i<n*n;i++)
    {
        if(poz[i].y-1>=1)
            if(alt[poz[i].y-1][poz[i].x]>alt[poz[i].y][poz[i].x])
                if(sol[poz[i].y-1][poz[i].x]<sol[poz[i].y][poz[i].x]+1)
                {
                    sol[poz[i].y-1][poz[i].x]=sol[poz[i].y][poz[i].x]+1;
                    if(maxim<sol[poz[i].y][poz[i].x]+1)
                    {
                        maxim=sol[poz[i].y][poz[i].x]+1;
                        pozi=poz[i].y-1;
                        pozj=poz[i].x;
                    }
                }
        if(poz[i].y+1>=1)
            if(alt[poz[i].y+1][poz[i].x]>alt[poz[i].y][poz[i].x])
                if(sol[poz[i].y+1][poz[i].x]<sol[poz[i].y][poz[i].x]+1)
                {
                    sol[poz[i].y+1][poz[i].x]=sol[poz[i].y][poz[i].x]+1;
                    if(maxim<sol[poz[i].y][poz[i].x]+1)
                    {
                        maxim=sol[poz[i].y][poz[i].x]+1;
                        pozi=poz[i].y+1;
                        pozj=poz[i].x;
                    }
                }
        if(poz[i].x-1>=1)
            if(alt[poz[i].y][poz[i].x-1]>alt[poz[i].y][poz[i].x])
                if(sol[poz[i].y][poz[i].x-1]<sol[poz[i].y][poz[i].x]+1)
                {
                    sol[poz[i].y][poz[i].x-1]=sol[poz[i].y][poz[i].x]+1;
                    if(maxim<sol[poz[i].y][poz[i].x]+1)
                    {
                        maxim=sol[poz[i].y][poz[i].x]+1;
                        pozi=poz[i].y;
                        pozj=poz[i].x-1;
                    }
                }
        if(poz[i].x+1>=1)
            if(alt[poz[i].y][poz[i].x+1]>alt[poz[i].y][poz[i].x])
                if(sol[poz[i].y][poz[i].x+1]<sol[poz[i].y][poz[i].x]+1)
                {
                    sol[poz[i].y][poz[i].x+1]=sol[poz[i].y][poz[i].x]+1;
                    if(maxim<sol[poz[i].y][poz[i].x]+1)
                    {
                        maxim=sol[poz[i].y][poz[i].x]+1;
                        pozi=poz[i].y;
                        pozj=poz[i].x+1;
                    }
                }
    }

    bkt(maxim,pozi,pozj);

    rezi[maxim]=pozi;
    rezj[maxim]=pozj;

    fout<<maxim+1<<'\n';
    for(i=0;i<=maxim;i++)
        fout<<rezi[i]<<' '<<rezj[i]<<'\n';
    return 0;
}

void bkt(int val,int i,int j)
{
    for(;val!=0;val--)
    {
        if(i-1>=1)
            if(sol[i-1][j]==val-1)
            {
                rezi[val-1]=i-1;
                rezj[val-1]=j;
                i--;
                continue;
            }
        if(i+1<=n)
            if(sol[i+1][j]==val-1)
            {
                rezi[val-1]=i+1;
                rezj[val-1]=j;
                i++;
                continue;
            }
        if(j-1>=1)
            if(sol[i][j-1]==val-1)
            {
                rezi[val-1]=i;
                rezj[val-1]=j-1;
                j--;
                continue;
            }
        if(j+1<=n)
            if(sol[i][j+1]==val-1)
            {
                rezi[val-1]=i;
                rezj[val-1]=j+1;
                j++;
                continue;
            }
    }
}