== include(page="template/taskheader" task_id="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.
Jocul Biscuit se joacă pe un caroiaj dreptunghiular cu _M_ linii și _N_ coloane de puncte. Pe rând, doi jucători desenează linii î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 liniile 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.
h2. 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.
Fișierul de intrare $biscuit.in$ ...
h2. 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.
În fișierul de ieșire $biscuit.out$ ...
h2. Restricții
* $2 ≤ M, N ≤ 1.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. biscuit.in |_. biscuit.out |_. Explicație |
| 5 6
10101
01000
10111
10011
01011
111111
100101
111000
010101
| 14
| !<problema/biscuit?biscuit.png!
|
table(example).
|_. biscuit.in |_. biscuit.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h2. Explicație
h3. 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.
...
== include(page="template/taskfooter" task_id="biscuit") ==
== include(page="template/taskfooter" task_id="biscuit") ==
