Kółko informatyczne

Wyprzedaż

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ę...

Wejście, wyjście

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:

• X oznacza półkę - tu nie można wchodzić.
• S oznacza wejście do sklepu - stąd zaczynasz podróż - jest tylko jedno S w całym sklepie
• D oznacza stoisko z CD-ROMami na wagę - to Twój cel - jest tylko jedno D w całym sklepie
• każde inne pole jest oznaczone cyfrą od 1 do 9, oznaczająca, ile czasu Ci zajmie przepchanie się przez to pole.

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ć.

Przykład

Dane:

5 5
S5213
2X2X5
51248
4X4X2
1445D

dają odpowiedź:

23

[Zgłoś rozwiązanie]   [Moje zgłoszenia]