Wstęp do programowania w C++

Na mapie znajduje się skarb, który musisz jak najszybciej znaleźć. Jak go znajdziesz, to czeka cię cenna nagroda. Dostaniesz szóstkę z programowania z informatyki :)

Mapa to kwadratowa macierz złożona ze znaków: # oraz o (mała litera o), gdzie # to skała, natomiast o to przestrzeń, po której można się poruszać. Na mapie znajdziesz także jeden znak b — jest to miejsce, w którym się znajdujesz, oraz jeden znak s, w którym znajduje się skarb. Nie wolno wychodzić poza mapę, lewy jej kraniec nie łączy się z prawym oraz góra nie łączy się z dołem. 

Twoim zadaniem jest znalezienie najkrótrzej ścieżki z punktu b do punktu s. Pamiętaj, że możesz poruszać się tylko po polach oznaczonych znakiem o idąc w góre, w dół, w lewo lub w prawo. Powodzenia!

Wejście

W pierwszym wierszu jedna liczba n określająca wielkość mapy. Liczba ta zawiera się w przedziale [3..1000].

W kolejnych n wierszach po n znaków tworzących mapę.

Wyjście

Jedna liczba będąca długością najkrótszej ścieżki lub -1, jeśli ścieżka nie istnieje. Przejście z jednego pola na drugie liczymy jako 1.

Przykład

Wejście:

4
##ob
oooo
o###
ooos

Wyjście:

9