dame2

Dame2

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

Poveste si cerinta...

Avem o tabla de sah ({$8 X 8 $}) din care au fost distruse unele patratele. Pe patratele care nu sunt distruse trebuie plasat un numar minim de dame astfel incat fiecare patratel care nu e distrus sa fie atacat si oricare doua dame nu trebuie sa se atace intre ele. O dama ataca o patratica daca se afla pe aceeasi linie, coloana sau diagonala (chiar daca intre ele exista patratele distruse).
 
h2. Cerinta
 
Calculati numarul minim de dame necesar si gasiti o pozitionare a acestora minim lexicografica.

h2. Date de intrare

...

Fisierul de intrare $dame2.in$ va contine 8 linii cu cate 8 caractere. Caracterul $i$ de pe linia $j$ va fi $0$ in cazul in care patratica nu a fost distrusa si va fi $1$ in caz contrar.

h2. Date de iesire

...

Pe prima linie a fisierului de intrare $dame2.out$ se va afisa $X$ numarul minim de dame necesar. Urmatoarea linie va contine $X$ perechi de numere $a$ $b$ semnificand ca trebuie pozitionata o dama pe linia $a$ si coloana {$b$}.

h2. Restrictii

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

* O pozitionare {$a{~1~} b{~1~} a{~2~} b{~2~} ... a{~X~} b{~X~}$} este mai mica lexicografic decat {$c{~1~} d{~1~} c{~2~} d{~2~} ... c{~X~} d{~X~}$} daca stringul obtinut prin concatenare {$a{~1~}b{~1~}a{~2~}b{~2~}...a{~X~}b{~X~}$} este mai mic lexicografic decat {$c{~1~}d{~1~}c{~2~}d{~2~}...c{~X~}d{~X~}$}

h2. Exemplu