s013

S013

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

Poveste şi cerinţă...

Cercetatorii din Rusia au inventat o noua arma pe care, in lipsa de inspiratie, s-au hotarat sa o denumeasca $S013$. Pentru a o testa, ei au construit un poligon( de dimensiune $N x M$) cu tinte. Arma poate fi plasata intr-o pozitie a matricei in care exista o tinta sau o urma, indreptata spre o directie( Nord, Sud, Est, Vest) si abia apoi se poate trage. In momentul in care un glont trece printr-un patrat ce contine o tinta, ea este distrusa si in acel loc ramane o urma. Un glont al acestei arme se opreste abia in momentul in care ajunge la o zona libera( fara urme/ tinte).
 
Cu toate acestea, arma are si o mica problema. Poate fi folosita de extrem de putine ori inainte de a se strica.
 
h2. Cerinta:
 
Tinand cont de faptul ca si Rusia a fost lovita de criza, cercetatorii ar vrea sa afle numarul minim de actionari astfel incat toate tintele sa fie distruse( pentru ca arma sa poate fi folosita in cat mai multe experimente).

h2. Date de intrare

Fişierul de intrare $s013.in$ ...

Fişierul de intrare $s013.in$ va contine pe prima linie numerele $N$ si $M$. Urmatoarele $N$ linii vor contine cate $M$ caractere: '.' in cazul unui loc liber si '*' in cazul unei tinte.

h2. Date de ieşire

În fişierul de ieşire $s013.out$ ...

În fişierul de ieşire $s013.out$ va contine pe prima linie numarul minim de actionari cerut.

h2. Restricţii

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

* $1 ≤ N ≤ 50$
* $1 ≤ M ≤ 50$
* Se considera ca glontul trece inclusiv prin pozitia in care este plasata arma.

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

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

| 4 4
@*.*.@
.***
***.
..*.
| 4

|

h3. Explicaţie
 
...
 

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

5933