1486: Малюк Смурф у лабіринті 2


Submit solution


Points:12
Time limit:0.5s
Memory limit:500M
Author:

Problem types

Малюк Смурф хоче дiстатися до Смурфетки i для цього йому треба подолати дорогу переповнену перешкодами та непрохiдними чагарниками. Для подолання перешкод малюк буде втрачати енергiю i тому йому треба знайти найлегший шлях. Татко Смурф завдяки своїм магiчним здiбностям створив план лiсу iз вказiвкою витрат енергiї при проходженнi кожного квадрата. Тепер Малюку Смурфу треба знайти марштур з найменшими витратами енергiї.

Формат вхідних даних

Перший рядок мiстить ширину w i висоту h плану. Жоден розмiр не перевищує 25. Наступнi h рядкiв мiстять w символiв кожен. Лiтера X вказує непрохiдний квадрат, лiтера S позначає положення малюка Смурфа, а лiтера D - квадрат, у якому знаходиться Смурфетка. Прохiднi квадрати позначенi цифрами вiд 1 до 9, що означають кiлькiсть енергiї, необхiдної для проходження цього квадрата. Iснує багато тестових випадкiв, якi роздiляються порожнiм рядком. Введення даних закiнчується шириною та висотою, рiвною 0 0. Багато у нашiй задачi - не бiльше 1000.

Формат вихідних даних

Ваша програма повинна вивести мiнiмальну кiлькостi енергiї, яка необхiдна малюку Смурфу для подорожi. Кожен тест виводити в окремому рядку. Рухатися по плану можна лише вертикально та горизонтально. Завжди iснує спосiб дiстатися до квадрату Смурфетки.

Приклад вхідних даних

4 3
X1S3
42X4
X1D2

5 5
S5213
2X2X5
51248
4X4X2
1445D

0 0

Приклад вихідних даних

4
23

Comments

There are no comments at the moment.