Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | regine2.in, regine2.out | Sursă | Happy Coding 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | regine2.out |
|---|---|
| 3 1 . 1 # 4 .#.. ##.. .#.# .#.# | 1 1 0 1 4 6 |
