Zadatak se može rešiti jednostavnom modifikacijom Dajkstrinog algoritma za pronalaženje najkraćeg puta od gornjeg levog polja, pa do svih ostalih polja, uključujući i poslednje, donje desno polje. Jedina razlika u odnosu na uobičajeni Dajkstrin algoritam se u slučaju da je poznato najmajnje rastojanje \(r_{uv}\) od čvora \(u\) do čvora \(v\) (najveća razlika visina na najboljem putu od \(u\) do \(v\)) i rastojanje \(r_{vw}\) od čvora \(v\) do njemu susednog čvora \(w\) (razlika visina), tada je najmanje rastojanje od čvora \(u\) do čvora \(v\) jednako \(\max(r_{uv}, r_{vw})\). Tada se vrednost rastojanja ažurira na osnovu dodele \(r_{uw} := \min(r_{uw}, \max(r_{uv}, r_{vw}))\).
“Težina” grane \((u, v)\) je u ovom primeru definisana kao razlika visina dva čvora koje ta grana spaja. “Dužina” puta \((v_0, v_1, \ldots, v_k)\) je ovde definisana kao maksimalna razlika visina čvorova na putu. “Zbir” dužine dva puta jednak je njihovom maksimumu. Ova metrika zadovoljava sledeća svojstva:
Može se dokazati da su ova svojstva dovoljna da osiguraju korektnost Dajkstrinog algoritma.
int najmanjeNapornaStaza(const vector<vector<int>>& visine) {
// dimenzije matrice
int m = visine.size(), n = visine[0].size();
// rastojanje od početnog do svakog drugog čvora pamtimo u matrici
vector<vector<int>> rastojanje(m, vector<int>(n, INF));
// podatak da li je do čvora određeno rastojanje pamtimo u matrici
vector<vector<bool>> resen(m, vector<bool>(n, false));
// red sa prioritetom koji koji sadrži trojke na čijem je prvom mestu
// dužina grane, a zatim čvor iz kog ta grana polazi
// (njegove koordinate)
priority_queue<tuple<int, int, int>,
vector<tuple<int, int, int>>,
greater<tuple<int, int, int>>> pq;
// rastojanje do početnog čvora je 0
rastojanje[0][0] = 0;
// krećemo od početnog čvora
pq.emplace(0, 0, 0);
while (!pq.empty()) {
// skidamo element sa vrha reda sa prioritetom
auto [tezina, v, k] = pq.top();
pq.pop();
// ako je do čvora na poziciji (v, k) ranije određen najkraći put,
// taj čvor preskačemo
if (resen[v][k])
continue;
// pamtimo da smo upravo odredili najkraći put do čvora na
// poziciji (v, k)
resen[v][k] = true;
// prolazimo kroz sve susede ovog čvora
int dv[] = {-1, 1, 0, 0};
int dk[] = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int vv = v + dv[i];
int kk = k + dk[i];
if (!(0 <= vv && vv < m && 0 <= kk && kk < n))
continue;
// do kojih je najkraće rastonja još nepoznato
if (resen[vv][kk])
continue;
// težina grane od trenutnog do susednog čvora
int razlika = abs(visine[vv][kk] - visine[v][k]);
// ažuriramo rastojanje do suseda ako je manje od dosadašnjeg
int novoRastojanje = max(rastojanje[v][k], razlika);
if (novoRastojanje < rastojanje[vv][kk]) {
rastojanje[vv][kk] = novoRastojanje;
pq.emplace(rastojanje[vv][kk], vv, kk);
}
}
}
// vraćamo najkraće rastojanje do ciljnog polja
return rastojanje[m-1][n-1];
}#include <iostream>
#include <vector>
#include <limits>
#include <queue>
#include <tuple>
using namespace std;
const int INF = numeric_limits<int>::max();
int najmanjeNapornaStaza(const vector<vector<int>>& visine) {
// dimenzije matrice
int m = visine.size(), n = visine[0].size();
// rastojanje od početnog do svakog drugog čvora pamtimo u matrici
vector<vector<int>> rastojanje(m, vector<int>(n, INF));
// podatak da li je do čvora određeno rastojanje pamtimo u matrici
vector<vector<bool>> resen(m, vector<bool>(n, false));
// red sa prioritetom koji koji sadrži trojke na čijem je prvom mestu
// dužina grane, a zatim čvor iz kog ta grana polazi
// (njegove koordinate)
priority_queue<tuple<int, int, int>,
vector<tuple<int, int, int>>,
greater<tuple<int, int, int>>> pq;
// rastojanje do početnog čvora je 0
rastojanje[0][0] = 0;
// krećemo od početnog čvora
pq.emplace(0, 0, 0);
while (!pq.empty()) {
// skidamo element sa vrha reda sa prioritetom
auto [tezina, v, k] = pq.top();
pq.pop();
// ako je do čvora na poziciji (v, k) ranije određen najkraći put,
// taj čvor preskačemo
if (resen[v][k])
continue;
// pamtimo da smo upravo odredili najkraći put do čvora na
// poziciji (v, k)
resen[v][k] = true;
// prolazimo kroz sve susede ovog čvora
int dv[] = {-1, 1, 0, 0};
int dk[] = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int vv = v + dv[i];
int kk = k + dk[i];
if (!(0 <= vv && vv < m && 0 <= kk && kk < n))
continue;
// do kojih je najkraće rastonja još nepoznato
if (resen[vv][kk])
continue;
// težina grane od trenutnog do susednog čvora
int razlika = abs(visine[vv][kk] - visine[v][k]);
// ažuriramo rastojanje do suseda ako je manje od dosadašnjeg
int novoRastojanje = max(rastojanje[v][k], razlika);
if (novoRastojanje < rastojanje[vv][kk]) {
rastojanje[vv][kk] = novoRastojanje;
pq.emplace(rastojanje[vv][kk], vv, kk);
}
}
}
// vraćamo najkraće rastojanje do ciljnog polja
return rastojanje[m-1][n-1];
}
int main() {
ios_base::sync_with_stdio(false);
int m, n;
cin >> m >> n;
vector<vector<int>> visine(m);
for (int i = 0; i < m; i++) {
visine[i].resize(n);
for (int j = 0; j < n; j++)
cin >> visine[i][j];
}
cout << najmanjeNapornaStaza(visine) << endl;
return 0;
}