choco

Choco

== include(page="template/taskheader" task_id="choco") ==

Poveste si cerinta...

Lui Bob ii place foarte tare ciocolata si nu se satura de ea niciodata. Imaginati-va bucuria lui cand parintii i-au spus ca ii vor cumpara multe bucati dreptunghiulare de ciocolata de ziua lui. O bucata de ciocolata este un dreptunghi $1x2$ sau $2x1$. Parintii lui Bob i-au cumparat, de asemenea, un tort, care poate fi reprezentat ca o matrice avand $M$ linii si $N$ coloane. Unele pozitii de pe tort sunt ocupate de lumanari, iar altele sunt goale. Parintii lui Bob l-au rugat sa puna pe tort cat mai multe bucati de ciocolata, in asa fel incat oricare $2$ bucati sa nu se suprapuna. Bob, insa, vrea sa pastreze cat mai multe bucati pentru el. De aceea, el vrea sa aseze pe tort un numar minim de bucati de ciocolata, pastrandu-le pe restul pentru el. Pentru ca mama si tata sa nu intre la banuieli, Bob vrea sa aseze bucatile de ciocolata in asa fel incat nici o alta bucata de ciocolata sa nu mai poata fi asezata pe tort (adica sa nu existe $2$ patratele libere adiacente pe orizontala sau verticala).
 
Determinati numarul minim de bucati de ciocolata ce trebuie asezate pe tort, astfel incat acestea sa nu se suprapuna si nici o alta bucata suplimentara sa nu mai poata fi asezata.

h2. Date de intrare

...

Prima linie a fisierului de intrare $choco.in$ contine $2$ numere intregi, separate prin cate un spatiu: $M$ si $N$. Urmatoarele $M$ linii vontin fiecare cate $N$ caractere, descriind tortul. Al $j$-lea caracter de pe a $i$-a dintre aceste $M$ linii poate fi ori '*' (cod ASCII 42), reprezentand o lumanare, ori '.' (cod ASCII 46), reprezentand o pozitie libera.

h2. Date de iesire

...

In fisierul de iesire $choco.out$ veti afisa numarul minim de bucati de ciocolata pe care le va aseza Bob pe tort.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ M ≤ 70$
* $1 ≤ N ≤ 7$

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

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

|5 5
.*..*
*....
..**.
**.*.
.**..
|4|

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

2288