Fişierul intrare/ieşire:s013.in, s013.outSursăad-hoc
AutorDin FolclorAdăugată dedushmiMihai-Alexandru Dusmanu dushmi
Timp execuţie pe test0.05 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/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.ins013.out
4 4
*.*.
.***
***.
..*.
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content