Cod sursa(job #2461645)

Utilizator deiubejanAndrei Bejan deiubejan Data 25 septembrie 2019 21:52:58
Problema Prefix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>
using namespace std;

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


#define cin fin
#define cout fout
/*
*/
const int MAXN=1025;
const int HMAX=16385;
int n;
int dp[MAXN][MAXN];
int v[MAXN][MAXN];
int dirx[]={-1,1,0,0};
int diry[]={0,0,-1,1};
int imaxi, jmaxi;
deque<pair<int,int>>rez;

void read()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>v[i][j];
}

bool verif(int i, int j)
{
    if(i<1||i>n||j<1||j>n)
        return 0;
    return 1;
}



void dfs(int i, int j)
{
    dp[i][j]=1;
    for(int q=0; q<4; q++)
    {
        int newi=i+dirx[q];
        int newj=j+diry[q];

        if(verif(newi,newj)&&v[i][j]>v[newi][newj])
        {
            if(dp[newi][newj]==0)
                dfs(newi,newj);
            dp[i][j]=max(dp[i][j],dp[newi][newj]+1);
        }
    }
}

void print()
{
    int maxi=dp[imaxi][jmaxi];
    cout<<maxi<<"\n";
    while(maxi--)
    {
        rez.push_front({imaxi,jmaxi});
        for(int q=0; q<4; q++)
        {
            int newi=imaxi+dirx[q];
            int newj=jmaxi+diry[q];

            if(verif(newi,newj)&&dp[imaxi][jmaxi]==dp[newi][newj]+1)
            {
                imaxi=newi;
                jmaxi=newj;
                break;
            }
        }
    }
    for(auto el:rez)
        cout<<el.first<<" "<<el.second<<"\n";
}


void solve()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            if(dp[i][j]==0)
                dfs(i,j);
            if(dp[i][j]>dp[imaxi][jmaxi])
            {
                imaxi=i;
                jmaxi=j;
            }
        }
    print();
}




int main()
{
    read();
    solve();

    return 0;
}