Moisil++ 2016, clasa a X-a · Clasa a IX-aOperații cu bițiProbleme cu operații cu biți
Problema MR
Cerință
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)șip2(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.
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
Lde linii și numărulCde coloane pentru harta labirintului, separate printr-un spațiu; - pe următoarele
Llinii se vor găsiCvalori de-1(reprezentând zid) sau0separate printr-un spațiu; - pe linia
L + 2se va găsi numărul de teleporturiT; - pe fiecare dintre următoarele
Tlinii se vor găsi câte patru numere de forma:L1 C1 L2 C2separate printr-un spațiu, reprezentând poziţiile de pe hartă ale teleporturilor. Rică poate să aleagă să se teleporteze din pozițiaL1 C1în pozițiaL2 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 ≤ 1000 ≤ T ≤ 100- Pentru fiecare set de date de intrare există soluție
- Pentru 50% din teste nu există teleporturi
Exemplu
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
8
Explicația exemplului
Un drum posibil este: (1, 1) → (2, 1) → (3, 1) → (3, 2) → (3, 3) → (4, 3) → (5, 3) → (5, 4) → (5, 5).
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;