Introduzione
Come avrete letto dal titolo del post, ho intenzione di illustrare brevemente due soluzioni che a mio parare risultano overkill per il livello delle territoriali per il problema “escursioni”.
Il problema è disponibile sulla piattaforma terry in cui potete accedere attraverso le credenziali di olinfo, mentre su wiki-olinfo è presente un editorial in cui sono spiegate le soluzioni più semplici.
Per chi ha intenzione di risolvere il problema ho realizzato questo piccolo grader per i/o.
#include <bits/stdc++.h>
using namespace std;
const int MAXH = 101, MAXW = 101;
int trovare_pericolo(int H, int W, int A[][MAXW]);
int main(){
int A[MAXH][MAXW];
int T;
cin >> T;
for(int t = 1; t <= T; t++){
int H, W;
cin >> H >> W;
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
cin >> A[i][j];
}
}
int ans = trovare_pericolo(H, W, A);
cout << "Case #" << t << ": " << ans << '\n';
}
return 0;
}
Ricerca Binaria
Prima di introdurre la ricerca binaria e su come adoperarla, iniziamo a trovare una soluzione a forza bruta. Il problema si può facilmente ridurre a trovare l’arco massimo minimo in un percorso qualsiasi tra la sorgente e la destinazione. Quindi una prima soluzione è per ogni peso possibile di un arco provo a raggiungere la destinazione utilizzando solamente archi minori e uguali del peso che sto testando. In questo modo otterremo una complessità di O(A_{i, j} (H W + 4 H W)) data dalla visita del grafo e dal numero di tentativi che potremmo imbatterci per raggiungere la soluzione. Per ottimizzare questa soluzione faremo uso della ricerca binaria, per chi è avvezzo con questa tecnica avrà già capito come applicarla ma per chi è nuovo lasciatemi fare una piccola introduzione.
L’uso più comune della ricerca binaria è la ricerca di un elemento all’interno di un vettore ordinato. Inizialmente si ha un range che copre l’intero vettore e si verifica che l’elemento intermedio sia quello cercato e in caso contrario si verifica se sia minore (o maggiore) in modo tale da poter scartare metà del range in cui cercare. Questo procedimento si ripete fin quando non si trova l’elemento o siano finiti gli elementi. In questo modo in O(log(N)) iterazioni (dove N è la grandezza del vettore) sapremo se l’elemento che stiamo cerando è stato trovato o meno.
Ma questo come ci aiuta a risolvere il nostro problema? Il cuore della ricerca binaria è il poter scartare deliberatamente alcuni elementi perché già sappiamo che essi rispecchiano determinate condizioni. Nel nostro caso sappiamo che se riuscissimo ad arrivare a destinazione con un peso x allora è possibile arrivare a destinazione con pesi x + 1, x + 2, x + 3, x + 4, \dots Ora possiamo ridurre il nostro numero di tentativi a log(A_{i,j}) ricercando il peso minimo con la ricerca binaria portando la complessità finale a O(log(A_{i, j}) (H W + 4 H W)) .
Vi consiglio di vedere il mio codice solo dopo aver provato a scrivere la vostra versione, ci sono alcuni trick che potrebbero tornarvi utili.
#include <bits/stdc++.h>
using namespace std;
const int MAXH = 101, MAXW = 101;
int trovare_pericolo(int H, int W, int A[][MAXW]);
int main(){
int A[MAXH][MAXW];
int T;
cin >> T;
for(int t = 1; t <= T; t++){
int H, W;
cin >> H >> W;
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
cin >> A[i][j];
}
}
int ans = trovare_pericolo(H, W, A);
cout << "Case #" << t << ": " << ans << '\n';
}
return 0;
}
bool visitato[MAXH][MAXW];
int moves[][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
int GetDif(int y1, int x1, int y2, int x2, int A[][MAXW]){
return abs(A[y1][x1] - A[y2][x2]);
}
void dfs(int y, int x, int H, int W, int dif, int A[][MAXW]){
visitato[y][x] = true;
for(int i = 0; i < 4; i++){
int cy = y + moves[i][0];
int cx = x + moves[i][1];
// Fuori dai confini
if(cy < 0 || cy >= H)continue;
if(cx < 0 || cx >= W)continue;
if(visitato[cy][cx] || GetDif(y, x, cy, cx, A) > dif)continue;
dfs(cy, cx, H, W, dif, A);
}
}
int trovare_pericolo(int H, int W, int A[][MAXW]){
int s = 0, e = 1e6 + 1, mid, f;
while(s <= e){
mid = s + (e - s) / 2;
memset(visitato, 0, sizeof(visitato));
dfs(0, 0, H, W, mid, A);
if(visitato[H - 1][W - 1]){
e = mid - 1;
f = mid;
}else{
s = mid + 1;
}
}
return f;
}
DSU
La seconda soluzione che vi propongo è la dsu che fa uso sempre della stessa riduzione del problema: trovare l’arco massimo minimo nel percorso tra la sorgente e la destinazione. Per chi non conoscesse questa struttura dati, la dsu è una struttura dati particolare che permette di unire elementi in insiemi e di trovare l’insieme di appartenenza di un determinato elemento con basse complessità.
L’idea generale è quella di considerare ogni nodo del grafo come un elemento e di verificare che la sorgente e la destinazione facciano parte dello stesso insieme. Ora il problema è come unire i vari elementi in modo tale da avere il peso minimo? Il peso minimo sarà dato sicuramente dagli archi col peso minore quindi non ci resta che ricavare tutti gli archi e ordinarli per peso. Una volta ordinati, partendo dagli archi con peso minore uniamo le estremità nello stesso insieme, fin quando la sorgente e la destinazione non risultano appartenenti allo stesso insieme. L’arco che permetterà l’unione sarà la soluzione del nostro problema. Complessità: O(H W log(H W)
L’idea è molto banale ma ci sono piccoli dettagli di implementazione che potrebbe rendere ostica la scrittura di questa soluzione. Il primo consiglio che propongo è di non prendere tutti i possibili archi da ogni nodo ma solo l’arco che si trova alla sua destra e in basso. In questo modo consideriamo tutti i possibili archi. L’altro consiglio è di numerare i nodi in modo tale da rimuovere la coppia ordinata per identificare un determinato nodo.
#include <bits/stdc++.h>
using namespace std;
const int MAXH = 101, MAXW = 101;
int trovare_pericolo(int H, int W, int A[][MAXW]);
int main(){
int A[MAXH][MAXW];
int T;
cin >> T;
for(int t = 1; t <= T; t++){
int H, W;
cin >> H >> W;
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
cin >> A[i][j];
}
}
int ans = trovare_pericolo(H, W, A);
cout << "Case #" << t << ": " << ans << '\n';
}
return 0;
}
class dsu{
private:
vector <int> id;
public:
dsu(int N){
id.resize(N, 0);
for(int i = 0; i < N; i++){
id[i] = i;
}
}
int FindSet(int N){
if(id[N] != N){
id[N] = FindSet(id[N]);
}
return id[N];
}
void UnionSet(int A, int B){
int Sa = FindSet(A);
int Sb = FindSet(B);
id[Sb] = Sa;
}
bool AreSameSet(int A, int B){
return FindSet(A) == FindSet(B);
}
};
int GetDif(int y1, int x1, int y2, int x2, int A[][MAXW]){
return abs(A[y1][x1] - A[y2][x2]);
}
int GetId(int y, int x, int H, int W){
return y * W + x;
}
int trovare_pericolo(int H, int W, int A[][MAXW]){
dsu DSU(H * W + 1);
vector <pair <int, pair <int, int> > > edges;
for(int i = 0; i < H; i++){
for(int j = 0; j < W; j++){
// arco a destra
if(j + 1 < W){
edges.push_back({GetDif(i, j, i, j + 1, A), {GetId(i, j, H, W), GetId(i, j + 1, H, W)}});
}
// arco in basso
if(i + 1 < H){
edges.push_back({GetDif(i, j, i + 1, j, A), {GetId(i, j, H, W), GetId(i + 1, j, H, W)}});
}
}
}
sort(edges.begin(), edges.end());
int S = GetId(0, 0, H, W);
int E = GetId(H - 1, W - 1, H, W);
int i = 0;
while(!DSU.AreSameSet(S, E)){
DSU.UnionSet(edges[i].second.first, edges[i].second.second);
i = i + 1;
}
return edges[i - 1].first;
}