Lista de probleme 78

Se dă o hartă de NxN care conține spații libere (notate cu '.') și spații ocupate (notate cu '#'). Să se răspundă la Q interogări de forma i1 j1 i2 j2, unde se dorește să se afle distanța minimă de la celula (i1, j1) la celula (i2, j2).

Să se scrie un program care gestionează o coadă de numere întregi. Inițial coada este vidă. Programul va citi de la tastatură o listă de operații, care pot fi:

• push X – adaugă valoarea întreagă X în coadă;
• pop – elimină elementul din coadă;
• front – afișează elementul de la începutul cozii.

Programul va realiza asupra cozii operațiile citite, în ordine. Afișările se fac pe ecran, câte o valoare pe linie.

Se consideră C o coadă de numere naturale, iniţial vidă. Se definesc 2 tipuri de operaţii.

Operaţia 1 : push X, adaugă elementul X în coadă. Dacă X există deja în coadă, se scot toate elementele din coadă, pana la întâlnirea lui, inclusiv X.

Exemplu: 
	C: 2 4 5 1 6
	Push 5
	C: 1 6 5 ( s-au scos 2, 4, 5).

Operaţia 2: query X, cere afişarea poziţiei elementului X în coada C. Dacă elementul nu există în coadă, se afişează -1.

Exemplu:
	C: 2 5 1 3 7
	Query 1
	Răspuns: 3

Se dau patru numere naturale n a x y. Să se afișeze elementele mulțimii M, cu următoarele proprietăți:

• toate elementele lui M sunt numere naturale mai mici sau egale cu n;
• a se află în M;
• dacă b se află în M, atunci b+x și b+y se află în M.

Se dă o matrice cu n linii și m coloane și elemente 0 sau 1, reprezentând planul unui teren în care 0 reprezintă o zonă accesibilă, iar 1 reprezintă o zonă inaccesibilă. O zonă a terenului are ca și coordonate linia și coloana corespunzătoare din matrice. Într-o zonă cunoscută a matricei se află un robot, iar în altă zonă, e asemenea cunoscută, se află o roboțică. Determinați numărul minim de pași prin care robotul va ajunge la roboțică. Dacă nu este posibil ca robotul să ajungă la roboțică, rezultatul va fi -1.

Ash este un antrenor Pokemon ambițios, setându-și scopul să devină cel mai bun. Din păcate, rivalul său, Gary, a furat startul și are Pokemoni mai puternici decât cei ai lui Ash.

Totuși, Ash nu se va da bătut chiar așa ușor! Are un plan de bătaie: în aventurile sale a găsit o clădire misterioasă care poate fi reprezentată ca o matrice de N x M, fiecare celulă reprezentând conținutul unei camere. În această clădire se află:

• Ash (codificat cu A): Ash se află inițial în această cameră
• Mewtwo (codificat cu M): cel mai puternic Pokemon cunoscut de om. Ash are deja un Master Ball, așa că îl va poate prinde pe Mewtwo cu ușurință.
• Gary (codificat cu G): a fost provocat de Ash la o bătălie de Pokemoni și îl așteaptă într-o anumită cameră
• cameră liberă (codificată cu _): Ash poate accesa această cameră
• cameră ocupată (codificată cu #): Ash nu poate accesa această cameră

Planul său constă în a-l prinde pe Mewtwo, după aceea în a-l confrunta pe Gary. Ash se poate deplasa în cele patru direcții cardinale (N, E, S, V). Știind că o deplasare se face într-o secundă, determinați numărul minim de secunde în care Ash poate ajunge la Mewtwo, apoi la Gary.

Se dă harta unui lac de formă dreptunghiulară, împărțit în n*m zone dispuse sub forma unei matrice cu n linii și m coloane. Zonele pot fi acoperite cu apă, sau pot fi zone de uscat. Zonele de uscat care sunt învecinate pe linie sau pe coloană formează insule sau peninsule. Peninsule conțin cel puțin o zonă de uscat pe marginea lacului (matricei), în timp ce insulele sunt situate în întregime în interiorul lacului.

Cunoscând harta lacului, determinați numărul de insule și numărul de peninsule.

Se consideră o clădire de formă dreptunghiulară, împărțită în n*m camere, dispuse sub forma unei matrice cu n linii și m coloane. Dintr-o cameră se poate trece în oricare dintre cele 4 camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.

În una dintre camere se află proprietarul clădirii, care dorește să afle, pentru fiecare dintre camere care este timpul minim necesar pentru a ajunge în acea cameră.

Se consideră harta unei suprafețe deșertice, dată sub forma unei matrice cu n linii și m coloane, formată din n*m zone. Fiecare zonă poate fi accesibilă sau inaccesibilă. Dintr-o zonă accesibilă se poate trece în altă zonă accesibilă învecinată cu prima pe linie sau pe coloană.

Un călător dorește să traverseze deșertul de la nord (prima linie) la sud(ultima linie). Pentru aceasta el poate sa aleagă oricare zonă accesibilă de pe prima line și dorește să ajungă pe ultima linie cu număr minim de pași.

Se dă o tablă dreptunghiulară formată din n linii și m coloane, definind n*m zone, unele dintre ele fiind libere, altele conținând obstacole. Într-o zonă precizată se află un șoarece care se poate deplasa pe tablă trecând din zona curentă în zona învecinată cu aceasta pe linie sau pe coloană. Scopul sau este să ajungă la o bucată de brânză aflată într-o zonă de asemenea precizată, fără a părăsi tabla, fără a trece prin zone care conțin obstacole și fără a trece de două ori prin aceeași zonă.

Determinați o modalitate prin care șoarecele poate să ajungă la bucata de brânză.