# PBinfo #4437 – arcade1 – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț Ernest a găsit în garajul familiei sale un joc Pacman. Labirintul din joc poate fi reprezentat ca o matrice cu N linii și N coloane. Pe fiecare linie și fiecare coloană există exact un obstacol. Vom nota cu (L, C) poziția de pe linia L și coloana C. Matricea este circulară: dacă Pacman se deplasează la dreapta din poziția (L, N), ajunge în (L, 1), iar dacă se deplasează la stanga din poziția (L, 1), ajunge în (L, N), pentru orice linie L din matrice. Similar, dacă se deplasează în sus din (1, C), ajunge în (N, C), respectiv dacă se deplasează în jos din (N, C), ajunge în (1, C), pentru orice coloană C. Inițial Pacman se află în (1, 1) și vrea sa ajungă în (N, N) unde se găsește un punct galben care îl va ajuta să învingă fantomele colorate. Regulile acestei versiuni de joc permit doar 4 tipuri de mișcări pentru Pacman, relative la poziția curentă: U – se deplasează în sus până se lovește de un obstacol sau a ajuns în (N, N). D – se deplasează în jos până se lovește de un obstacol sau a ajuns în (N, N). L – se deplasează la stânga până se lovește de un obstacol sau a ajuns în (N, N). R – se deplasează la dreapta până se lovește de un obstacol sau a ajuns în (N, N). De remarcat faptul că, odată ajuns în (N, N), Pacman nu va mai putea părăsi această poziție, indiferent de mișcările ulterioare pe care le-ar face. Cerința Problema este formată din doua cerințe: Cerința 1. Se citește un șir de mișcări format din literele U, D, L, R, ce descriu în ordine mișcările lui Pacman. Deplasându-se conform acestui șir, va ajunge Pacman din (1, 1) la punctul galben de coordonate (N, N)? Cerința 2. Care este numărul minim de mișcări U, D, L, R prin care Pacman poate ajunge din (1, 1) la punctul galben de coordonate (N, N)? Date de intrare Fișierul de intrare arcade.in conține va conține T teste. Pe prima linie a fișierului se află numărul cerinței C ∈ {1, 2} și numărul de teste T. Pe prima linie a fiecărui test i se află Ni, dimensiunea matricei pentru testul i, iar pe a doua linie sunt Ni numere P1, P2, …, PNi. Pentru fiecare 1 ≤ j ≤ Ni, obstacolul j are coordonatele (j, Pj). Dacă C = 1, pe a treia linie a fiecărui test se află mișcările scrise ca un șir de caractere, fără spații, din mulțimea {U, D, L, R}. Date de ieșire Pe fiecare dintre cele T linii ale fișierului de ieșire arcade.out se va afla răspunsul pentru testul corespunzător. În cazul în care C = 1, se va afișa Won, dacă răspunsul la cerință este afirmativ, respectiv Lost, dacă răspunsul este negativ. Dacă C = 2, se va afișa numărul minim de mișcări cerut, sau -1 dacă nu se poate ajunge din (1, 1) în (N,N). Restricții și precizări 1 ≤ T ≤ 50.000 2 ≤ Ni, pentru orice test 1 ≤ i ≤ T N1 + N2 + ... + NT ≤ 100.000 (unde N1 + N2 + ... + NT reprezintă suma tuturor N-urilor dintr-un fișier de intrare) 1 ≤ Pj ≤ Ni și Pj ≠ Pk pentru orice j ≠ k. Pentru C = 1, suma lungimilor șirurilor de mișcări din toate cele T teste nu depășește 1.000.000. Se garantează că (1, 1) și (N, N) nu sunt blocate de un obstacol (P1 ≠ 1 și PN ≠ N). Pentru 18 puncte, C = 1, N1 + N2 + ... + NT ≤ 1000, suma lungimilor șirurilor de mișcări din toate cele T teste nu depășește 10.000 Pentru 19 puncte, C = 1 Pentru 33 puncte, C = 2, N1 + N2 + ... + NT ≤ 1000 Pentru 30 puncte, C = 2 Exemplul 1: arcade.in 1 3 5 2 1 3 5 4 LDLDL 4 3 1 4 2 RDRUL 6 3 2 1 6 5 4 RURU arcade.out Won Lost Won Explicație Drumul pentru primul test: Exemplul 2: arcade.in 2 3 5 2 1 3 5 4 6 6 5 4 3 2 1 6 3 2 1 6 5 4 arcade.out 4 -1 4 Explicație Pentru primul test, șirul LDRU este una din cele mai scurte variante. ## Cod sursă C++ ```cpp /** Popescu Stefan-Alexandru - 100p O(N) **/ #include using namespace std; const int nmax = 1e5; int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; /// DRUL int cerinta, n; int xPtY[nmax + 2], yPtX[nmax + 2]; /// x e abscisa, y e ordonata int minDist[nmax + 2][4]; /// indexate dupa x; R-U-L-D int drumMinFin; pair nextUp(int x, int y){ /// creste a doua if(x == n - 1 && yPtX[x] < y) /// ajungem direct la tinta return make_pair(-1, -1); return make_pair(x, yPtX[x]); } pair nextDown(int x, int y){ /// scade a doua if(x == n - 1 && yPtX[x] > y) /// ajungem direct la tinta return make_pair(-1, -1); return make_pair(x, yPtX[x]); } pair nextRight(int x, int y){ /// creste prima if(y == n - 1 && xPtY[y] < x) return make_pair(-1, -1); return make_pair(xPtY[y], y); } pair nextLeft(int x, int y){ /// scade prima if(y == n - 1 && xPtY[y] > x) return make_pair(-1, -1); return make_pair(xPtY[y], y); } inline void updatePositionWith(int xNxt, int ornNxt, int xAct, int ornAct, queue > & q){ if(xNxt != -1){ if(minDist[xNxt][ornNxt] > minDist[xAct][ornAct] + 1) minDist[xNxt][ornNxt] = minDist[xAct][ornAct] + 1, q.emplace(xNxt, ornNxt); } else{ if(drumMinFin > minDist[xAct][ornAct] + 1) drumMinFin = minDist[xAct][ornAct] + 1; } } void bfs(){ memset(minDist, 127, 4 * 4 * n); drumMinFin = 1e9; queue > q; pair per = nextLeft(0, 0); minDist[per.first][0] = 1; q.emplace(per.first, 0); per = nextDown(0, 0); minDist[per.first][1] = 1; q.emplace(per.first, 1); per = nextRight(0, 0); minDist[per.first][2] = 1; q.emplace(per.first, 2); per = nextUp(0, 0); minDist[per.first][3] = 1; q.emplace(per.first, 3); while(!q.empty()){ auto elem = q.front(); q.pop(); // cerr << elem.first << " " << elem.second << "\n"; pair per = nextLeft((elem.first + dx[elem.second] + n) % n, (yPtX[elem.first] + dy[elem.second] + n) % n); updatePositionWith(per.first, 0, elem.first, elem.second, q); per = nextDown((elem.first + dx[elem.second] + n) % n, (yPtX[elem.first] + dy[elem.second] + n) % n); updatePositionWith(per.first, 1, elem.first, elem.second, q); per = nextRight((elem.first + dx[elem.second] + n) % n, (yPtX[elem.first] + dy[elem.second] + n) % n); updatePositionWith(per.first, 2, elem.first, elem.second, q); per = nextUp((elem.first + dx[elem.second] + n) % n, (yPtX[elem.first] + dy[elem.second] + n) % n); updatePositionWith(per.first, 3, elem.first, elem.second, q); } } void solve(){ // cin >> cerinta; cin >> n; for(int i = 0; i < n; i++){ int y; cin >> y; /// daca se oglindeste dupa diagonala principala se umbla mai jos y--; // cerr << i << " " << y << "\n"; yPtX[i] = y; xPtY[y] = i; } // cerr << "\n"; // for(int i = 0; i < n; i++){ // cerr << xPtY[i] << " " << yPtX[i] << "\n"; // } // cerr << "\n\n\n"; if(cerinta == 1){ string s; cin >> s; int x1 = 0, x2 = 0; for(auto &x:s){ // cerr << x1 << " " << x2 << "\n"; switch (x) { case 'D': x = 'R'; break; case 'U': x = 'L'; break; case 'L': x = 'D'; break; case 'R': x = 'U'; break; default: break; } if(x == 'D'){ auto per = nextDown(x1, x2); if(per.first == -1){ cout << "Won\n"; return; } x2 = (per.second + 1) % n; } else if(x == 'L'){ auto per = nextLeft(x1, x2); if(per.first == -1){ cout << "Won\n"; return; } x1 = (per.first + 1) % n; } else if(x == 'U'){ auto per = nextUp(x1, x2); if(per.first == -1){ cout << "Won\n"; return; } x2 = (per.second - 1 + n) % n; } else if(x == 'R'){ auto per = nextRight(x1, x2); if(per.first == -1){ cout << "Won\n"; return; } x1 = (per.first - 1 + n) % n; } } // cerr << x1 << " " << x2 << "\n"; cout << "Lost\n"; } else{ bfs(); cout << (drumMinFin == 1e9 ? -1 : drumMinFin) << "\n"; } } int main(){ // ios_base::sync_with_stdio(false), cin.tie(0), std::cout.tie(0); freopen("arcade.in", "r", stdin); freopen("arcade.out", "w", stdout); cin >> cerinta; int q = 1; cin >> q; while(q--){ solve(); } return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4437) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4437/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4437/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)