Pod Warszawą otworzyli nowy sklep z akcesoriami elektronicznymi. Postanowiłeś się wybrać na otwarcie, jednak okazało się, że nie tylko Ty wpadłeś na tak genialny pomysł. Ludzi jest pełno, a Ty chcesz się dostać do stoiska z CD-ROMami na wagę. Patrząc na sklep przez szybę narysowałeś plan sklepu, teraz tylko pozostało wyciągnąć z plecaka laptopa i napisać program, który Ci znajdzie najszybszą drogę dostania się do stoiska z CD-ROMami na wagę...
Sklep ma kształt prostokąta x na y, 1 <= x,y <= 25. W pierwszej linii wejścia są liczby x i y, oddzielone pojedynczą spacją. Kolejne y linii zawiera po x znaków każda, każdy znak opisuje pojedyncze pole w sklepie:
Przechodzić możesz tylko między polami sąsiadującymi bokiem. Przejście przez pole S i D zajmuje zaniedbywalnie mało czasu.
W jednej jedynej linijce wyjścia powinieneś wypisać jedną liczbę całkowitą - minimalny czas potrzebny do dostania się do stoiska z CD-ROMami na wagę. Załóż, że zawsze jakoś się da tam przepchać.
Dane:
5 5 S5213 2X2X5 51248 4X4X2 1445D
dają odpowiedź:
23
[Zgłoś rozwiązanie] [Moje zgłoszenia]