O nouă epidemie de gripă amenință să îmbolnăvească o mare parte din populație, iar zonele cele mai afectate sunt orașele cele mai aglomerate, unde oamenii pot lua ușor contact cu persoane bolnave.
Epidemia încă nu a cuprins și orașul tău, dar te uiți îngrijorat la știri și îți imaginezi că oricine a venit dintr-o călătorie poate să fie purtător. Așa că ai desenat o hartă cu toate casele din oraș și acum vrei să vezi care e distanța minimă de la casa în care stă prietenul tău venit din delegație de peste ocean până la fiecare din casele din oraș.
Orașul arată ca o matrice de n linii și m coloane, iar fiecare pătrățel din matrice conține o casă. Astfel, fiecare casă va avea 4 vecini, dacă nu se află chiar la marginea orașului.
Să presupunem că matricea are dimensiune de 6 x 5, iar prietenul tău locuiește în casa de la coordonate (2, 3). Dacă desenăm o schemă a orașului sub forma unei matrice, ea va arăta ca în desenul de mai jos. Fiecare valoare din matrice reprezintă distanța până la focar:
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4
5 4 3 4 5
6 5 4 5 6
Cerință
Ți se dau numărul de linii (n) și de coloane (m) ale matricii care reprezintă orașul tău. În plus, ți se mai dă indicele de linie și de coloană al casei în care stă vecinul tău, suspect de gripă.
Afișează o matrice de n x m care să conțină, pe fiecare poziție (i, j), un număr întreg reprezentând distanța minimă de la casa vecinului venit din delegație până la casa de pe poziția (i, j).
Date de intrare
Pe prima linie se vor afla numerele n și m, separate printr-un spațiu, reprezentând dimensiunile matricei. Pe a doua linie se vor afla alte 2 numere întregi separate prin spațiu, reprezentând indicele de linie și de coloană al casei vecinului.
Date de ieșire
Se va afișa o matrice de n linii și m coloane, cu elementele de pe o linie separate prin spații. Fiecare element din matrice reprezintă distanța minimă până la focar, conform cerinței.
Restricții și precizări
1 ≤ n, m ≤ 100
Numerotarea liniilor și coloanelor începe de la 1
1 ≤ indicele de linie al casei vecinului ≤ n
1 ≤ indicele de coloană al casei vecinului ≤ m
Date de intrare
6 5
2 3
Date de iesire
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4
5 4 3 4 5
6 5 4 5 6
◘ Coordonata x
◘ Coordonata y
◘ Distanta fata de focar
Introducem in coada (x_focar, y_focar, 0).
Cat timp coada nu e goala scoatem elementul din capul cozii, verificam daca nu cumva e deja vizitat, salvam in matrice distanta pe coordonatele respective si introducem vecinii din nord, sud, est vest, cu distanta marita cu 1 fata de elementul curent.
Distanta manhattan intre doua puncte A(x,y) si B(x,y) :
distanta manhattan(A,B) = |A.x - B.x| + |A.y - B.y|
Răspunsuri la întrebare
#include <iostream>
using namespace std;
int distanta_MH(int ax, int ay, int bx, int by) {
return abs(ax - bx) + abs(ay - by);
}
int main() {
int n, m;
int lin_focar, col_focar;
//Citeste dimensiuni tabla
cin >> n >> m;
//Citeste locatie focar
cin >> lin_focar >> col_focar;
//Afisare si generare tabela
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << distanta_MH(i, j, lin_focar, col_focar) << " ";
}
cout << endl;
}
}
► Explicatie :
Generam si afisam o matrice in care valoarea pentru fiecare element este distanta Manhattan dintre locatia curenta si locatia focarului.
Distanta MH intre doua puncte este suma dintre diferenta dintre abscisele punctelor si diferenta dintre ordonata punctelor. Se foloseste in foarte multe probleme de info in care deplasarea in matrice se face doar stanga, dreapta, jos, sus.
Te invit sa cauti mai multe informatii pe internet despre acest topic.
