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 cifre $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 este mai mic lexicografic. Perechile vor fi separate prin exact un spatiu. In cazul in care nu exita nici o solutie fisierul de iesire va contine cifra 0 pe prima linie.

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

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

| 00000000
  00111111
  01011111
  01101111
  01110111
  01111011
  01111101
  00000000
| 2
1 1 8 2

|
h3. Explicatie

...

Punem o regina pe prima linie si prima coloana si inca o regina pe ultimul rand si a doua coloana.

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

2052