Fişierul intrare/ieşire:	jocdesah.in, jocdesah.out	Sursă	RAUCoder 2020
Autor	Daniela Alexandra Crisan	Adăugată de	Daniela Alexandra Crisan •RAUCoder
Timp execuţie pe test	0.025 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

JocDeSah

RAU-Gigel se gândeşte la un joc cu piesele de şah. El desenează o tablă de şah sub forma unei matrici pătratice de latură N şi aşează în fiecare dintre cele N x N celule câte o piesă de şah. Se consideră că dispune de N X N exemplare din fiecare piesă posibilă (regi, regine, ture, nebuni, cai, pioni), iar culoarea nu este relevantă. RAU-Gigel se întreabă care este numărul minim de căsuţe (celule) prin care trebuie să treacă un rege oarecare ca să ajungă la o regină oarecare. Regele se poate deplasa câte o celulă în patru direcţii posibile: N, E, S, V.

Dar asta nu e tot. La începutul jocului, toţi regii au 16 vieţi. Atunci când RAU-Gigel mută un rege (oarecare) peste primul pion, acesta pierde o viaţă. Vestea bună este că, după aceea, regele respectiv poate lua oricâţi pioni fără ca numărul său de vieţi să fie afectat. Când ia un cal, regele pierde două vieţi, dar după aceea poate lua, fără pierderi, oricâţi cai. La fel se întâmplă şi în cazul nebunilor, primul nebun îl costa patru vieţi şi, respectiv al turelor, care îl costă opt vieţi.

RAU-Gigel doreşte să afle ce rege să aleagă şi pe ce traseu trebuie să meargă acesta către o regină oarecare, astfel încât la sfârşitul jocului să îi rămână cât mai multe vieţi, iar traseul să fie cât mai scurt.

Se cer:
a) Care este numărul maxim de vieţi cu care rămâne regele ales?
b) Prin câte căsuţe trece traseul de lungime minimă? Ce rege mută şi pe ce traseu? Dacă există mai multe drumuri de lungime minimă, atunci se va determina drumul mai mic alfanumeric. (O celulă este mai mică alfanumeric decât altă celulă dacă se află pe un rând cu indice mai mic sau se află pe acelaşi rând cu cea de-a doua, dar pe o coloană cu indice mai mic)

Date de intrare

Fişierul de intrare jocdesah.in conţine pe prima linie un număr natural A. Pentru toate testele de intrare, numărul A poate avea doar valoarea 1 sau valoarea 2. Pe al doilea rând se găseşte numărul natural N, cu semnificaţia din enunţ. Pe următoarele N linii se află câte N litere mari cu următoarea semnificaţie: P – pion, C – cal, N - nebun, T - tură, Q – regină şi K – rege. Caracterele de pe fiecare rând nu au spaţii între ele.

Date de ieşire

Dacă valoarea lui A este 1, se va rezolva numai punctul a) din cerinţă. În acest caz, fişierul de ieşire jocdesah.out va conţine un singur număr natural ce reprezintă numărul de vieţi care îi rămân la sfârşitul jocului regelui ales de RAU-Gigel.

Dacă valoarea lui A este 2, se va rezolva numai punctul b) din cerinţă. În acest caz, fişierul de ieşire jocdesah.out va conţine pe prima linie numărul natural K ce reprezintă numărul de căsuţe prin care trece regele ales (se numără atât căsuţa din care pleacă, cât şi cea în care ajunge), apoi pe următoarele K rânduri sunt perechi de forma i j (separate cu un singur spaţiu) unde i şi j reprezintă linia, respectiv coloana celulelor prin care trece regele (în ordinea de deplasare). Indexarea rândurilor şi coloanelor se face de la 1 la N.

Restricţii

2 ≤ N ≤ 100
In fiecare test există cel puţin o literă K şi cel puţin o literă Q
Pentru rezolvarea corectă a primei cerinţe se acordă 45 de puncte

Exemplul 1

jocdesah.in	jocdesah.out
2 6 PCQPNP PCCCCP QNPKPK PCKPPP NKPPPP NNPPQP	5 3 4 3 5 4 5 5 5 6 5

Explicaţie

RAU-Gigel va alege să mute regele de pe poziţia 3 4. Drumul va trece prin 5 celule (va număra inclusiv celulele de plecare şi sosire), iar acestea sunt: 3 4, 3 5, 4 5, 5 5, 6 5. În drumul său a luat doar pioni, deci a pierdut o singură viaţă, i-au rămas 15:

* * * * * *
* * * * * *
* * * K P *
* * * * P *
* * * * P *
* * * * Q *

Se observă că mai există un drum de lungime 5 care îl costă tot o singură viaţă:

* * * * * *
* * * * * *
* * * K * *
* * * P P *
* * * * P *
* * * * Q *

Drumul este:
3 4, 4 4, 4 5, 5 5, 6 5, dar el este mai mic alfanumeric decât:
3 4, 3 5, 4 5, 5 5, 6 5 (perechea 3 5 e mai mică alfanumeric decât perechea 4 4).

De asemenea, un alt drum este: 3 4, 3 3, 3 2, 3 1:

* * * * * *
* * * * * *
Q N P K * *
* * * * * *
* * * * * *
* * * * * *

acesta chiar mai scurt (trece prin numai 4 căsuţe), totuşi pe acest drum regele ar ataca un pion şi un nebun, care l-ar costa 1 + 4 = 5 vieţi şi ar rămâne cu numai 11, de aceea nu îl va alege.