Cerința

Cătălin s-a pierdut iarăși într-o matrice de N linii și M coloane în care unele celule sunt blocate. Cătălin nu găsește ieșirea așa că s-a decis să caute o comoară. El are o harta pe care a desenat-o când era mic și decide să o urmeze. Pe harta este scris un șir format din caracterele U, R, D, L. În fiecare secundă Cătălin se va deplasa în una dintre cele 4 celule adiacente. Presupunând că la secunda S Cătălin se află în celula i, j el se va mișcă în funcție de al S-lea caracter de pe harta în felul următor: pentru U el va păși în celula i - 1, j; pentru R el va păși în celula i, j + 1; pentru D el va păși în celula i + 1, j, iar pentru L, el va păși în celula i, j - 1.

Dacă celula în care trebuie să pășească este în afara matricei sau este blocată, atunci Cătălin va sta pe loc în acea secunda. În ce celulă ajunge Cătălin?

Date de intrare

Pe prima linie a fișierului de intrare labirint4.in se vor afla trei numere naturale N, M și K. Pe următoarele K linii se vor afla cate 2 numere reprezentând linia și coloana unei celule blocate. Pe următoarea linie se vor afla 2 numere naturale reprezentând linia, respectiv coloana de pe care începe Cătălin să se miște. Pe ultima linie se va afla numărul de caractere din șirul de pe hartă urmat de acele caractere.

Date de ieșire

În fișierul de ieșire labirint4.out se vor afla două numere reprezentând linia și coloana pe care ajunge Cătălin.

Restricții și precizări

1 ≤ lungimea șirului de pe hartă ≤ 10000
Pentru 20 de puncte 1 ≤ N, M ≤ 10000 și K = 0
Pentru alte 60 de puncte: 1 ≤ N, M ≤ 500 și 1 ≤ K ≤ N * M
Pentru restul de puncte: 1 ≤ N, M ≤ 10000 și 1 ≤ K ≤ 1000

Exemplu

labirint4.in

4 5 7
1 3
1 5 
2 1 
2 4 
2 5 
3 1
3 2
2 2
11
ULRDDRDRDLU

labirint4.out

3 3

Explicație

Traseul lui Catalin este:
(2, 2) → (1, 2) → (1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (3, 4) → (4, 4) → (4, 3) → (3, 3)

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 labirint4:

#include <fstream> 
#include <cstring> 
#include <unordered_set> 
#define Nmax 102 
using namespace std; 
  
ifstream f("labirint4.in"); 
ofstream g("labirint4.out"); 
  
int n,x,y,X,Y,m,Q,K,lg; 
string s; 
int dx[255],dy[255]; 
unordered_set<int> M; 
bool OK(int a, int b) 
{ 
    if (a>=1 && a<=n && b>=1 && b<=m) 
        return 1; 
    return 0; 
} 
  
  
int main() 
{ 
    dx['U'] = dy['L'] = -1; 
    dx['D'] = dy['R'] = 1; 
  
    f>>n>>m>>K; 
    for (int i=1;i<=K;i++) 
    { 
        f>>x>>y; 
        M.insert(x*100000+y); 
    } 
    f>>X>>Y; 
    f>>lg>>s; 
    for (auto it : s) 
    { 
        int X2 = X + dx[it]; 
        int Y2 = Y + dy[it]; 
        if (OK(X2,Y2) && !M.count(X2*100000+Y2)) 
            X = X2,Y = Y2; 
    } 
    g<<X<<' '<<Y; 
    return 0; 
}

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 #2341 labirint4

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2341 labirint4 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!

Rezolvare completă PbInfo #2341 labirint4