Lista de probleme 2

Se consideră un caroiaj format din n linii și n coloane, fiecare element din caroiaj fiind o literă mică din alfabetul englez. Să se constuiască șirul de caractere obținut prin parcurgerea caroiajului pe chenare dinspre exteriorul spre interiorul caroiajului, fiecare chenar fiind parcurs în sensul arcelor de ceas, pornind din colțul stânga sus al fiecărui chenar. Determinați cea mai lungă secvență de caractere situate pe poziții alăturate în șirul construit, care este simetrică. Dacă există mai multe astfel de secvențe de lungime maximă, se va determina ultima dintre ele.

Vasilică vizitează cetățile medievale. Fiind curios, el încearcă să descopere pasajele secrete și ascunzătorile. Din nefericire, s-a rătăcit și a ajuns într-o sală din care nu poate ieși decât trecând printr-un labirint. Există o hartă a labirintului, o matrice de n linii și m coloane, un element din această matrice reprezentând o cameră. Deplasarea în labirint se poate face numai prin camerele adiacente pe orizontală și verticală. Intrările în labirint sunt notate cu A, ieșirile cu C, iar camerele zidite (inaccesibile) cu Z. Ieșirea din labirint se poate face din una din camerele C, în fiecare astfel de cameră existând câte un elicopter încuiat. Toate elicopterele se deschid cu aceeași cheie, câte un exemplar al cheii aflându-se în camerele B. Trecerea în altă cameră va dura 1 unitate de timp. Pentru a ieși din labirint Vasilică intră pe una din intrările notate cu A, ia cheia dintr-o cameră B și iese din labirint printr-o cameră C. El va intra în camera A la timpul 1. Camerele de tip A pot fi situate oriunde pe hartă. În drumul de la o cameră de tip A către o cameră de tip B se poate trece printr-o cameră de tip C fără a se ieși din labirint. Ajutați-l pe Vasilică să iasă cât mai repede din labirint.