| Fişierul intrare/ieşire: | dame2.in, dame2.out | Sursă | Summer Challenge 2007, runda 3 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dame 2
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).
Cerinta
Calculati numarul minim de dame necesar si gasiti o pozitionare a acestora minim lexicografica.
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.
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.
Restrictii
- O pozitionare a1 b1 a2 b2 ... aX bX este mai mica lexicografic decat c1 d1 c2 d2 ... cX dX 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.
Exemplu
| dame2.in | dame2.out |
|---|---|
| 00000000 00111111 01011111 01101111 01110111 01111011 01111101 00000000 | 2 1 1 8 2 |
Explicatie
Punem o regina pe prima linie si prima coloana si inca o regina pe ultimul rand si a doua coloana.
