Rezolvare completă PbInfo #1913 mr

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema mr:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1913 mr

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1913 mr de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!