Fişierul intrare/ieşire:dame2.in, dame2.outSursăSummer Challenge 2007, runda 3
AutorCosmin Silvestru NegruseriAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.indame2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content