Se citeste o matrice cu caracterele '.' (celula libera), '#' (obstacol, prin care focul nu se propaga) si '*' (celula cu foc; pot exista mai multe). La fiecare unitate de timp, focul se extinde simultan din toate celulele aprinse catre celulele libere vecine pe orizontala si verticala. Determinati timpul minim necesar pentru ca toate celulele libere accesibile sa fie cuprinse de foc, folosind un BFS multi-sursa pornind din toate celulele cu foc. Daca exista cel putin o celula libera care nu poate fi niciodata atinsa de foc, afisati -1.
- Date de intrare
- Pe prima linie se citesc n si m, numarul de linii si de coloane ale matricei. Urmeaza n linii, fiecare continand un sir de m caractere.
- Date de iesire
- Se afiseaza timpul minim (numarul de unitati de timp) necesar propagarii complete, sau -1 daca nu este posibila.
- Restrictii
- 1 <= n, m <= 30, exista cel putin o celula cu foc
Exemple
Exemplul 1
Intrare
3 3 *.. ... ...
Iesire
4
Exemplul 2
Intrare
3 3 *.# .#. #..
Iesire
-1