Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | s013.in, s013.out | Sursă | ad-hoc |
| Autor | Din Folclor | Adăugată de |  Mihai-Alexandru Dusmanu •dushmi |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
S013
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.
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).
Date de intrare
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.
Date de ieşire
În fişierul de ieşire s013.out va contine pe prima linie numarul minim de actionari cerut.
Restricţii
- 1 ≤ N ≤ 50
- 1 ≤ M ≤ 50
- Se considera ca glontul trece inclusiv prin pozitia in care este plasata arma.
Exemplu
| s013.in | s013.out |
|---|---|
4 4*.*..*** ***. ..*. | 4 |
