Cod sursa(job #2950164)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 3 decembrie 2022 09:36:01
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
int a[1025][1025];
int dp[1025][1025];

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int dfs (int x, int y)
{
    if (dp[x][y] != -1)
        return dp[x][y];
    dp[x][y] = 1;
    for (int k=0; k<4; k++)
    {
        int i = x + dx[k], j = y + dy[k];
        if (i > 0 && i <= n && j > 0 && j <= n && a[i][j] > a[x][y])
            dp[x][y] = max(dp[x][y], dfs(i, j) + 1);
    }

    return dp[x][y];
}

void print (int x, int y)
{
    out << x << ' ' << y << '\n';
    if (dp[x][y] == 1)
        return;
    for (int k=0; k<4; k++)
    {
        int i = x + dx[k], j = y + dy[k];
        if (i > 0 && j > 0 && i <= n && j <= n && dp[i][j] == dp[x][y] - 1)
        {
            print(i, j);
            return;
        }
    }
}

int main()
{
    in >> n;

    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
            in >> a[i][j], dp[i][j] = -1;
    }

    int ans = 1;

    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (dp[i][j] == -1)
                {
                    dfs(i, j), ans = max(ans, dp[i][j]);
                }
        }
    }

    out << ans << '\n';

    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (dp[i][j] == ans)
            {
                print(i, j);
                return 0;
            }
        }
    }

    return 0;
}