== 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, 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) si nu isi poate schimba directia.
 
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