# PBinfo #1913 – mr – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Rică se joacă în fiecare seară The MazeRunnerVladVersion, joc pe care îl vom numi pentru simplitatea problemei MR. Jocul constă în găsirea unei căi de scăpare dintr-un labirint care conține:


ziduri prin care Rică nu va putea să treacă;
zero sau mai multe teleporturi cu ajutorul cărora deplasarea între două puncte precizate p1(x1, y1) și p2(x2, y2) se face într-un minut, dacă se doreşte acest lucru;
zone libere, trecerea din zona curentă într-o zonă învecinată se poate face pe direcția celor patru puncte cardinale. Deplasarea se va face într-un minut.

Rică pleacă din colțul stânga-sus al labirintului și doreşte să ajungă în colțul dreapta-jos.

El știe că are o teză în ziua următoare, așa că vă cere ajutorul vouă, programatorilor, și vă roagă să aflați timpul minim în care poate să ajungă din colțul stânga-sus în colțul dreapta-jos al labirintului.

Date de intrare
Fișierul de intrare mr.in conține:


numărul L de linii și numărul C de coloane pentru harta labirintului, separate printr-un spațiu
pe următoarele L linii se vor găsi C valori de -1 (reprezentând zid) sau 0 separate printr-un spațiu
pe linia L+2 se va găsi numărul de teleporturi T
pe fiecare dintre următoarele T linii se vor găsi câte patru numere de forma: L1 C1 L2 C2 separate printr-un spațiu, reprezentând poziţiile de pe hartă ale teleporturilor. Rică poate să aleagă să se teleporteze din poziția L1 C1 în poziția L2 C2.

Date de ieșire
Fișierul de ieșire mr.out va conține pe prima linie timpul minim necesar lui Rică pentru a parcurge labirintul.

Restricții și precizări

2 ≤ n, m ≤ 100
0 ≤ T ≤ 100
Pentru fiecare set de date de intrare există soluție.
Pentru 50% din teste nu există teleporturi.

Exemplul 1
mr.in

5 5
 0  0 -1 0 0 
 0 -1  0 0 0 
 0  0  0 0 0
-1 -1  0 0 0
 0  0  0 0 0
 0
mr.out

8
Explicație
Un drum minim posibil este:

(1, 1) → (2, 1) → (3, 1) → (3, 2) → (3, 3) → (4, 3) → (5, 3) → (5, 4) → (5, 5)
Exemplul 2
mr.in

5 6	
 0  0  0  0 -1  0
 0  0 -1 -1  0  0
-1  0  0  0 -1  0
-1  0 -1  0  0  0
-1 -1 -1  0  0  0
2
2 2 4 5
4 2 2 5
mr.out

5
Explicație
Un drum minim posibil este:

(1, 1) → (1, 2) → (2, 2) → (4, 5) → (4, 6) → (5, 6).
Între pozițiile (2,2) și (4,5) s-a utilizat primul teleport.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream cin("mr.in");
ofstream cout("mr.out");
int cost, minim[105][105], linii, coloane, j, i, matrice[105][105], teleportere, coada_i[10000], coada_j[10000], in, sf, iul, jul;
int pereche[1005][1005], cat;
int dir_i[] = {0, -1, 0, 1, 0};
int dir_j[] = {0, 0, 1, 0, -1};
struct copac
{
    int li, ci, ls, cs;
}teleporter[1005];
int main()
{
    cin >> linii >> coloane;
    for(i=1; i <= linii; i++)
    {
        for(j=1; j <= coloane; j++)
        {
            cin >> matrice[i][j];
            if(matrice[i][j] == 0)
            matrice[i][j] = 1;
        }
    }
    for(i=0; i <= linii+1; i++)
    {
        matrice[i][0] = -1;
        matrice[i][coloane+1] = -1;
    }
    for(i=0; i <= coloane+1; i++)
    {
        matrice[0][i] = -1;
        matrice[linii+1][i] = -1;
    }
    cin >> teleportere;
    for(i=1; i <= teleportere; i++)
    {
        cin >> teleporter[i].li >> teleporter[i].ci >> teleporter[i].ls >> teleporter[i].cs;
        pereche[teleporter[i].li][teleporter[i].ci] = i;
        pereche[teleporter[i].ls][teleporter[i].cs] = i;
    }
    coada_i[1] = 1;
    coada_j[1] = 1;
    minim[1][1] = matrice[1][1];
    in = 1;
    sf = 1;
    while(in <= sf)
    {
        for(j=1; j <= 4; j++)
        {
            iul = coada_i[in] + dir_i[j];
            jul = coada_j[in] + dir_j[j];
            if(matrice[iul][jul] != -1)
            {
                cost = minim[coada_i[in]][coada_j[in]] + matrice[iul][jul];
                if(minim[iul][jul] == 0 || minim[iul][jul] > cost)
                {
                    minim[iul][jul] = cost;
                    sf++;
                    coada_i[sf] = iul;
                    coada_j[sf] = jul;
                }
            }
        }
        cat = pereche[coada_i[in]][coada_j[in]];
        if(cat != 0)
        {
            if(coada_i[in] != teleporter[cat].li || coada_j[in] != teleporter[cat].ci)
            {
                iul = teleporter[cat].li;
                jul = teleporter[cat].ci;
            }
            else
            {
                iul = teleporter[cat].ls;
                jul = teleporter[cat].cs;
            }
            cost = minim[coada_i[in]][coada_j[in]] + 1;
            if(cost <= minim[iul][jul] || minim[iul][jul] == 0)
            {
                minim[iul][jul] = cost;
                sf++;
                coada_i[sf] = iul;
                coada_j[sf] = jul;
            }
        }
        in++;
    }
    /*for(i=1; i <= linii; i++)
    {
        for(j=1; j <= coloane; j++)
        {
            cout << minim[i][j]-1 << ' ';
        }
        cout << '\n';
    }*/
    cout << minim[linii][coloane]-1;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1913)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1913/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1913/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)