Lista de probleme 38

Oraşele Nordemos şi Suderim sunt separate de un munte foarte înalt. Inginerul Negrimon a fost desemnat să construiască un drum prin munte care să unească cele două oraşe. Harta care i s-a pus la dispoziţie descrie muntele ca o matrice cu N linii şi M coloane numerotate de la 1 la N, respectiv de la 1 la M . Un drum reprezintă o succesiune de elemente din matrice cu proprietatea că oricare două elemente consecutive sunt alăturate, pe linie sau pe coloană. Un drum uneşte oraşul Nordemos (linia 1) şi oraşul Suderim (linia N). Valorile din matrice reprezintă densităţile rocilor din munte în acele zone. Pentru fiecare drum posibil se poate calcula valoarea dmax, egală cu densitatea maximă a rocilor pe care le traversează. Negrimon trebuie să construiască un drum pentru care valoarea dmax este cea mai mică.

Ajută-l pe Negrimon să afle cea mai mică dintre densităţile dmax corespunzătoare drumurilor care unesc Nordemos şi Suderim în condiţiile de mai sus.

Scrieți un program care citește un număr natural N, valorile matricei și pozițiile inițiale ale jucătorilor și afișează la ieșire răspunsul la Q întrebări de forma: “Care este primul moment de timp după care avem cel puțin P celule colorate în matrice?”. În cazul în care pentru o întrebare nu se vor putea colora P celule libere (după oricât de mult timp), se va afișa ca răspuns pentru acea întrebare valoarea -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.

Marciuc este un băiat foarte neastâmpărat. El refuză să învețe informatică, așa că înainte de fiecare oră el pleacă pentru a explora noul său liceu. La plecare le promite colegilor lui că o să treacă pe la magazin înainte de a se întoarce în clasă, pentru a avea ce să mănânce în pauza următoare. Însă, dacă va ajunge în clasă în mai mult de T secunde, va întarza la ora așa că în acest caz va folosi o ruta directă spre clasă.

Liceul poate fi reprezentat sub forma unei matrice cu n linii și n coloane. Există 3 tipuri de celule:

• celulă liberă, pe unde băiatul poate avansa, o mutare durând o secundă;
• celulă ocupată de un zid, pe unde băiatul nu poate avansa;
• celulă în care se află o scurtătură, ce îl duce într-o secundă de la poziția, x1 y1, la poziția x2 y2 sau invers;

Fiind dat numărul n de linii și de coloane, coordonatele celulelor ocupate de zid și coordonatele scurtăturilor, se cere să se afișeze numărul de secunde în care Marciuc reușește să ajungă în clasă, trecând și pe la magazin. Dacă magazinul nu este accesibil sau daca va ajunge în clasă in mai mult de T secunde, atunci el nu va mai merge la magazin și se va afișa numărul de secunde în care acesta ajunge de la poziția lui la clasă. De asemenea, se va afișa și traseul folosit.

Se consideră o clădire de formă dreptunghiulară, formată din n*m camere dispuse sub forma unei matrice cu n linii și m coloane. Anumite camere sunt ocupate şi nu pot fi vizitate, celelalte sunt libere și pot fi vizitate. Dintr-o cameră se poate trece în altă cameră dacă ambele sunt libere și se învecinează pe linie sau pe coloană.

În anumite camere sunt paznici. Din motive de securitate, paznicii se pot deplasa din camera inițială în anumite camere libere din apropiere, dar fără a se îndepărta la o distanță mai mare decât o valoare cunoscută. Fiecare paznic va verifica periodic camerele libere în care poate ajunge.

Să se determine numărul de camere din clădire care nu sunt verificate de niciun paznic.

Se consideră o matrice cu N linii și N coloane, numerotate de la 1 la N, care memorează doar valori 0 și 1. Se dau de asemenea coordonatele a trei componente din această matrice. Să se determine lungimea minimă a unui drum care pleacă din poziția (1,1), trece obligatoriu prin cele trei componente date (nu contează în ce ordine) și apoi ajunge în poziția (N, N), drum care trece doar prin componente marcate cu 0 și învecinate pe linii și coloane.

Din fiecare celulă, să se afișeze distanța minimă la cel mai apropiat punct de referință.

Gigel este elev în clasa a XII-a la Liceul Teoretic “Ion Luca” din Vatra Dornei. Acesta, știind că urmează examenul de Bacalaureat și că nu a învățat nimic, s-a hotărât să plece de acasă să își găsească un rost în lume. După zile bune de mers, lipsit de energie, flămând și însetat, acesta a făcut un popas și s-a gândit că era mai bine să nu plece de acasă, motiv pentru care s-a hotărât să se întoarcă. Este cunoscut faptul că în pădurile dornene locuiesc atât Yeti, cât și Bigfoot, precum și mulți vârcolaci. Gigel, fiind un dornean adevărat, cunoaște coordonatele zonelor unde aceștia locuiesc și dorește să se întoarcă acasă pe drumul cel mai scurt, evitându-i pe aceștia.

Cunoscând suprafața regiunii în care se află Gigel și casa acestuia (care poate fi reprezentată printr-un tablou bidimensional cu n linii și m coloane, în care fiecare zonă are coordonatele x și y), coordonatele casei (X1, Y1) și coordonatele locului de popas (X2, Y2), coordonatele zonelor în care locuiesc Yeti (XY, YY) și Bigfoot (XB, YB), precum și coordonatele (X, Y) ale celor K zone în care locuiesc vârcolacii, se cere să îl ajutați pe Gigel să găsească lungimea D a celui mai scurt drum spre casă.

Fie o matrice cu n linii (numerotate de la 1 la n) și m coloane (numerotate de la 1 la m) ce conține doar literele a și b. Se definește un drum de la o poziție (xs, ys) la o alta (xf, yf) ca fiind o succesiune de pași care pornește din coordonatele (xs, ys) și ajunge în (xf, yf) și care trece numai prin componente care memorează litera a. La fiecare pas, de la o poziţie (i, j) se poate trece într-una din poziţiile (i+1, j), (i-1, j), (i, j+1), (i, j-1). Lungimea drumului este dată de numărul de componente care compun drumul.

Având la dispoziție q întrebări date sub forma a patru numere naturale xs ys xf yf, trebuie să răspundeți pentru fiecare întrebare care este lungimea minimă a unui drum de la (xs, ys) la (xf, yf) care trece numai prin componente ce memorează litera a. Dacă un astfel de drum nu există, veți afișa valoarea –1.

Se consideră un castel de formă dreptunghiulară, alcătuit din n*m camere dispuse pe n linii și m coloane. Intrarea în castel este în camera de coordonate (1,1), ieșirea în camera de coordonate n,m, unele camere sunt închise, dintr-o cameră se poate trece în camerele învecinate pe linie și pe coloană, iar unele camere sunt ocupate de zmei gripați, fiecare zmeu afectând camera sa și camere aflate în jurul său la distanța mai mică sau egală cu k.

Pentru a câștiga inima Ilenei Cosânzeana, Făt-Frumos trebuie să traverseze castelul. Deoarece nu se pricepe la informatică vă roagă pe voi să determinați care este lungimea minimă a unui traseu care traversează castelul, trece doar prin camere deschise și nu trece prin camere afectate de zmei.