Cerința

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 și precizări

• 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

2
6
PCQPNP
PCCCCP
QNPKPK
PCKPPP
NKPPPP
NNPPQP

jocdesah.out

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:

\( \star \star \star \star \star \star \)
\( \star \star \star \star \star \star \)
\( \star \star \star \) K P\( \star \)
\( \star \star \star \star \) P\( \star \)
\( \star \star \star \star \) P \( \star \)
\( \star \star \star \star \) Q \( \star \)

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

\( \star \star \star \star \star \star \)
\( \star \star \star \star \star \star \)
\( \star \star \star \) K \( \star \star \)
\( \star \star \star \) P P\( \star \)
\( \star \star \star \star \) P \( \star \)
\( \star \star \star \star \) Q \( \star \)

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:

\( \star \star \star \star \star \star \)
\( \star \star \star \star \star \star \)
QN P K \( \star \star\)
\( \star \star \star \star \star \star \)
\( \star \star \star \star \star \star \)
\( \star \star \star \star \star \star \)

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.

Exemplul 2:

jocdesah.in

1
6
PCQPNP
PCCCCP
QNPKPK
PCKPPP
NKPPPP
NNPPQP

jocdesah.out

15