Wstęp do algorymów
Pożar lasu
W lesie wybuchł pożar!
Las można przedstawić jako prostokąt $n \times m$ składający się z $nm$ kwadratów jednostkowych. W każdym kwadracie jednostokwym albo nie ma nic, albo rośnie drzewo. Dodatkowo niektóre drzewa zajęły się ogniem! Teraz w każdej sekundzie z każdego płonącego drzewa ogień rozprzestrzenia się na drzewo nad nim, pod nim, na lewo od niego i na prawo od niego. Ile sekund minie, zanim cały las stanie w płomieniach?
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby $n$ i $m$. Następne $n$ wierszy zawiera po $m$ znaków, które tworzą opis lasu. Znak . oznacza, że w danym miejscu nie ma nic. Znak + oznacza, że rośnie drzewo, które jeszcze się nie pali, a znak # oznacza, że rośnie drzewo zajęte ogniem.
Wyjście
Na wyjściu powinna znaleźć się jedna liczba sekund, które pozostały do całkowitego zajęcia się lasu. Jeżeli las nigdy całkowicie się nie zajmie, wypisz $-1$.
Ograniczenia
- $1 \le nm \le 10^6$
- W lesie znajduje się co najmniej jedno drzewo.
Przykłady
Wejście 1
3 5
#++.#
++#.+
....+
Wyjście 1
2
Wejście 1
3 5
##.##
#.+.#
##.##
Wyjście 1
-1