Pagini recente » Cod sursa (job #2389836) | Cod sursa (job #2399338) | Cod sursa (job #1468089) | Cod sursa (job #1485511) | Cod sursa (job #2962136)
#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;
}