regine2

Regine2

== include(page="template/taskheader" task_id="regine2") ==

Poveste si cerinta...

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.

h2. 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.

h2. 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.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 30$
* $1 ≤ N ≤ 8$

h2. Exemplu
table(example). |_. regine2.in |_. regine2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|3
1
.
1
#
4
.#..
##..
.#.#
.#.#
|1 1
0 1
4 6

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="regine2") ==

2354