Joc de șah

RAU-Gigel a terminat cursurile online pe ziua de astăzi. El tot la jocuri se gândește, de această dată la un joc cu piesele de șah. El desenează o tablă de șah sub forma unei matrici pătratice de dimensiune $N$ și așează în fiecare dintre cele $N \times N$ celule câte o piesă de șah. Se consideră că dispune de $N \times 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, RAU-Gigel are $15$ vieți. Atunci când RAU-Gigel mută un rege (oarecare) peste primul pion, el pierde o viață. Vestea bună este că, după aceea, RAU-Gigel 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 costă patru vieți și, respectiv al turelor, care îl costă opt vieți.

RAU-Gigel dorește să afle care este cel mai scurt drum de la un rege oarecare către o regină oarecare, dar cu condiția ca la sfârșitul jocului să îi rămână cât mai multe vieți.

Cerință

1. Care este numărul maxim de vieți care îi rămân lui RAU-Gigel?
2. 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

Se citește din fișierul jocdesah.in un număr natural $A$. Pentru toate testele de intrare, numărul $A$ poate avea doar valoarea $1$ sau valoarea $2$. Apoi se mai citește un rând pe care 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 1 din cerință. În acest caz, se va afișa în fișierul jocdesah.out un singur număr natural ce reprezintă numărul de vieți care îi rămân lui RAU-Gigel la sfârșitul jocului.

Dacă valoarea lui $A$ este $2$, se va rezolva numai punctul 2 din cerință. În acest caz, se va afișa în fișierul jocdesah.out, 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).

Restricții și precizări

• $2 \le N \le 100$
• În fiecare test există cel puțin o literă K și cel puțin o literă Q.
• Prima cerința valorează 45 de puncte.

Exemplul 1

jocdesah.in

1
6
PCQPNP
PCCCCP
QNPKPK
PCKPPP
NKPPPP
NNPPQP

jocdesah.out

14

Exemplul 2

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

Ambele exemple descriu aceeași tablă de șah.

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 $14$.

Se observă că mai există un drum de lungime $5$ care îl costă tot o singură viață: $(3,4)$, $(4,4)$, $(4,5)$, $(5,5)$, $(6,5)$. Acesta este însă mai mare alfanumeric decât drumul ales de RAU-Gigel (perechea $(3,5)$ e mai mică alfanumeric decât perechea $(4,4)$), de aceea nu îl va alege.

De asemenea, un alt drum este: $(3,4)$, $(3,3)$, $(3,2)$, $(3,1)$, acesta chiar mai scurt (trece prin numai $4$ căsuțe), totuși pe acest drum RAU-Gigel ar ataca un pion și un nebun, care l-ar costa $1 + 4 = 5$ vieți și ar rămâne cu numai $10$, de aceea nu îl va alege.