Fişierul intrare/ieşire:regine2.in, regine2.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.5 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Regine2

Se da o tabla de sah de dimensiune NxN. Pe aceasta tabla, unele patratele sunt libere, iar altele sunt blocate. Determinati care este numarul maxim de regine care pot fi plasate pe tabla de sah, astfel incat oricare doua regine sa nu se atace una pe alta. O regina poate fi plasata numai pe un patratel liber. Doua regine se ataca una pe alta daca sunt pe aceeasi linie, coloana sau diagonala si toate patratelele dintre cele 2 regine (de pe linia, coloana sau diagonala respectiva) sunt libere. Fie Q numarul maxim de regine care pot fi asezate pe tabla. In plus, trebuie sa determinati si numarul de posibilitati de a aseza cele Q regine pe tabla.

Date de intrare

Prima linie a fisierului de intrare regine2.in contine numarul intreg T, reprezentand numarul de teste. Urmatoarele linii contin descrierile celor T teste. Prima linie din cadrul fiecarui test contine numarul intreg N, reprezentand dimensiunea tablei de sah. Urmatoarele N linii contin cate N caractere, reprezentand descrierea fiecarei linii a tablei de sah. Caracterul '.' reprezinta un patratel liber, iar caracterul '#' reprezinta un patratel blocat.

Date de iesire

Pentru fiecare test afisati in fisierul de iesire regine2.out cate o linie continand 2 numere intregi: Q si P. Q reprezinta numarul maxim de regine ce pot fi plasate pe respectiva tabla de sah, iar P reprezinta numarul de posibilitati de a plasa Q regine pe tabla de sah.

Restrictii

  • 1 ≤ T ≤ 30
  • 1 ≤ N ≤ 8

Exemplu

regine2.inregine2.out
3
1
.
1
#
4
.#..
##..
.#.#
.#.#
1 1
0 1
4 6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content