| Fişierul intrare/ieşire: | jucarie.in, jucarie.out | Sursă | ad-hoc |
| Autor | Ciprian Oprisa | Adăugată de |  Ciprian Oprisa •cypry |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Jucărie
Gigel a primit de la părinţii lui o jucărie interesantă, sub forma unei matrici de 3 pe 3, cu 9 butoane. Fiecare buton poate fi alb sau negru şi îşi schimbă culoarea atunci când este apăsat. Din neatenţie, Gigel a scăpat jucăria pe jos, iar aceasta s-a defectat, schimbându-şi comportamentul. Astfel, atunci când un buton este apăsat, nu se schimbă doar propria culoare, ci şi culorile butoanelor existente din vecinătatea acestuia (sus, jos, stânga şi dreapta).
În exemplul de mai sus, Gigel începe cu toate butoanele albe şi apasă pe întâi pe buntonul de pe linia 1, coloana 2. Toate butoanele de pe linia 1 şi butonul de pe linia 2, coloana 2, devin negre. Apoi, Gigel apasă pe butonul de pe linia 1, coloana 3. Butoanele 2 şi 3 de pe linia 1 devin albe, deoarece înainte erau negre, iar butonul de pe linia 2, coloana 3 devine negru.
Gigel se întreabă cum poate aduce cele 9 butoane la culorile dorite, din cât mai puţine apăsări, ştiind că la început toate sunt albe. Scrieţi un program care pentru o cofiguraţie dată, calculează numărul minim de apăsări necesare.
Date de intrare
Fişierul de intrare jucarie.in conţine pe prima linie numărul de teste T. Fiecare test este format din exact 3 linii cu câte 3 caractere fiecare. Caracterele de pe fiecare linie sunt fie 'A' (reprezentând un buton alb) fie 'N' (reprezentând un buton negru).
Date de ieşire
În fişierul de ieşire jucarie.out se va tipări câte o linie pentru fiecare test, conţinând numărul minim de apăsări de butoane necesare pentru a obţine configuraţia dată în test, pornind de la toate butoanele albe. Dacă configuraţia dintr-un test nu se poate obţine, se va tipări -1.
Restricţii
- 1 ≤ T ≤ 100
Exemplu
| jucarie.in | jucarie.out |
|---|---|
| 2 NNN ANA AAA NAA ANN AAA | 1 2 |
