Fişierul intrare/ieşire:biscuit.in, biscuit.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie600 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Biscuit

Jocul Biscuit se desfăşoară pe un caroiaj dreptunghiular cu M linii şi N coloane de puncte. Pe rând, doi jucători trasează segmente între două puncte vecine pe orizontală sau pe verticală. Jucătorul care închide un pătrat (de latură 1) primeşte un punct şi mai mută o dată. Când toate segmentele au fost trasate, câştigă jucătorul care a închis mai multe pătrate.

Dându-se o tablă pe care s-au făcut deja nişte mutări, să se determine câte pătrate poate închide jucătorul care este la mutare.

Date de intrare

Fişierul de intrare biscuit.in conţine, pe prima linie, numerele M şi N.

Pe următoarele M linii sunt descrise segmentele orizontale. Fiecare linie conţine N-1 caractere. Al j-lea caracter de pe linia i este 1 sau 0 după cum al j-lea segment orizontal de pe linia i a fost trasat sau nu.

Pe ultimele M-1 linii sunt descrise segmentele verticale. Fiecare linie conţine N caractere. Al j-lea caracter de pe linia i este 1 sau 0 după cum al j-lea segment vertical de pe linia i a fost trasat sau nu.

Date de ieşire

În fişierul de ieşire biscuit.out se va scrie numărul de pătrate pe care le poate închide jucătorul la mutare.

Restricţii

  • 2 ≤ M, N ≤ 1.000

Exemplu

biscuit.inbiscuit.outExplicaţie
5 6
10101
01000
10111
10011
01011
111111
100101
111000
010101
14

Explicaţie

În figura de mai sus, segmentele negre sunt cele date la intrare. Jucătorul la mutare poate trasa segmentele verzi pentru a închide, în ordine, pătratele 1-14 (ordinea nu este unică). Segmentele gri sunt cele rămase netrasate după mutare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici