Cod sursa(job #2962141)

Utilizator indmium_Voicu Buhai Imperiu indmium_ Data 7 ianuarie 2023 20:39:28
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 1024;
int n, m[N + 2][N + 2], dp[N + 2][N + 2];
int diri[] = {-1, 0, 1, 0}; // N, E, S, V
int dirj[] = {0, 1, 0, -1}; // N, E, S, V

bool in_bounds(int i, int j){
    return (i >= 1 && i <= n && j >= 1 && j <= n);
}

void dfs(int i, int j){
    dp[i][j] = 1;
    for(int dir = 0; dir < 4; dir++){
        int x = i + diri[dir], y = j + dirj[dir];
        if(in_bounds(x, y) && m[x][y] > m[i][j]){
            if(!dp[x][y]) dfs(x, y);
            dp[i][j] = max(dp[i][j], dp[x][y] + 1);
        }
    }
}

int main(){
    fin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            fin >> m[i][j];
    int lmax = -1, l, c;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(!dp[i][j]) dfs(i, j);
            if(dp[i][j] > lmax){
                lmax = dp[i][j];
                l = i;
                c = j;
            }
        }
    }
    fout << lmax << '\n';
    for(int i = 0; i < lmax; i++){
        fout << l << ' ' << c << '\n';
        int d, maxi_dp = -1;
        for(int dir = 0; dir < 4; dir++){
            int x = l + diri[dir], y = c + dirj[dir];
            if(in_bounds(x, y) && m[x][y] > m[l][c] && dp[x][y] > maxi_dp){
                d = dir;
                maxi_dp = dp[x][y];
            }
        }
        l += diri[d];
        c += dirj[d];
    }
    return 0;
}