Alpin
Cerință:
Un alpinist se află într-o regiune muntoasă codificată sub forma unei matrici pătratice de dimensiune N, fiecare element al matricii reprezentând altitudinea respectivei porțiuni de teren. Alpinistul își poate porni traseul din orice punct al regiunii ( deci de la oricare dintre elementele matricii ) și poate termina acest traseu oriunde. El poate merge pe oricare din direcțiile {N, S, E, V} cu condiția să nu părăsească regiunea. In plus, trebuie să urce în permanență, sau, altfel spus, altitudinea regiunii curente sa fie strict mai mică decât altitudinea regiunii următoare de pe traseu. Să se determine cel mai lung traseu pe care îl poate face alpinistul.
Rezolvare:
Aceasta este o problemă în care pentru a obține punctaj maxim este nevoie să apelăm la tehnica memoizării. Matricea B va reține lungimea maximă a unui traseu care se termină în poziția (i,j). Pentru deplasarea în matricea A vom folosi doi vectori de direcție Dx si Dy, iar matricea B se va construi în funcție de elementele vecine poziției pe care se află alpinistul.
#include <iostream>
using namespace std;
const int maxn = 1030;
const int Dx[]={-1, 0, 1, 0};
const int Dy[]={0, 1, 0, -1};
int A[maxn][maxn], B[maxn][maxn], n;
int Climb(int x, int y) {
if (B[x][y] > 0) {
return B[x][y];
}
int xx, yy, i;
for (i = 0; i < 4; i++) {
xx = x + Dx[i];
yy = y + Dy[i];
if (A[xx][yy] > A[x][y]) {
int next_step = Climb(xx, yy);
if (next_step > B[x][y]) {
B[x][y] = next_step;
}
}
}
B[x][y]++;
return B[x][y];
}
void Print_route(int x, int y) {
cout << x << " " << y << "\n";
int xx, yy, i, ok = 1;
for (i = 0; i < 4 && ok; i++) {
xx = x + Dx[i];
yy = y + Dy[i];
if (B[xx][yy] == B[x][y] - 1 && A[x][y] < A[xx][yy]) {
ok = 0;
Print_route(xx, yy);
}
}
}
int main() {
ios_base :: sync_with_stdio (false);
int i, j, xs, ys, lg = 0;
cin >> n;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
cin >> A[i][j];
}
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
Climb(i, j);
}
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (lg < B[i][j]) {
lg = B[i][j];
xs = i;
ys = j;
}
}
}
cout << lg << "\n";
Print_route(xs, ys);
return 0;
}