@v0dka

Описание
Петя долго что-то чертил на небольшом листе в клетку, после чего, продемонстрировал его Васе.
- Смотри, это лабиринт, - сказал Петя, - и я готов поспорить, что ты не сможешь найти из него самую короткую дорогу.
Васе срочно нужна помощь программиста.

Задача
По заданной карте лабиринта (размера N x M) найдите самый кратчайший путь из точки A в точку B. Учтите, что каждая клетка имеет метку, которая соответствует времени, которое нужно затратить, чтобы пройти по ней. Также есть непроходимые клетки. За пределы лабиринта выходить нельзя. Из каждой клетки, можно пройти в соседние по горизонтали или вертикали (если они не являются непроходимыми). То есть, возможно перейти в соседнюю клетку, если она имеет общее ребро с текущей.

Входные данные
В первой строке 2 целых числа N и M через пробел (3<=N,M<=100). В следующих N cтроках по M символов без пробелов:
1-9 - время, которое нужно затратить, чтобы пройти по клетке (проходимая клетка);
# - стена (непроходимая клетка);
A - клетка старта (всегда присутствует в схеме);
B - клетка выхода из лабиринта (может быть где угодно в схеме лабиринта).
A и В всегда присутствуют в схеме лабиринта, и всегда в единственном экземпляре.

Выходные данные
Одно целое число - наименьшее время, необходимое для того, чтобы добраться из клетки A в клетку B.

Пример входных данных
Пример выходных данных
P.S. Добрые люди, помогите с алгоритмом

0

@Dani

Поиск в ширину в графе.

0

@v0dka

Dani, Кажется я начинаю понимать о чём ты), если можно, то хотелось бы подробнее

0

@Dani

v0dka, смотри: идем из начальной вершины, добавляем в очередь все вершины, которые являются соседними с текущей и т.д., пока не дойдем до конца. И если для вершины i есть соседняя v, то длина пути до нее - длина до i + время. И в последней ячейке и будет ответ. Не добавлять вершину в очередь, если она уже посещена, или это стена.

1

@v0dka

Dani, спасибо... ты мне ещё шире глаза открыл завтра попробую решить... если будут вопросы или ничего не получится, в личку напишу или сюда)

0

valeriikozlov

не совсем правильный алгоритм. Вот тест:
4 3
##B
111
1#9
11A
Для ячейки [2][3] будет ситуация, что она уже посещена (имеет значение 10), но ее все-таки нужно заносить в очередь снова.

1

@Dani

valeriikozlov, и я так понимаю, ей не уменьшать расстояние во второй раз?

0

valeriikozlov

наоборот, во второй раз ей нужно уменьшать расстояние, иначе не вычислим:
На самом деле, для одной ячейки, используя алгоритм из поста №4, значение может изменяться (уменьшаться) несколько раз (даже больше 3-х раз). Поэтому нужно или использовать алгоритм из 4 поста (но с условием добавлять уже пройденные вершины, если для них уменьшилось значение, а значит размер очереди намного больше N*M), или еще один алгоритм (но это в другой раз, если описанный алгоритм не пройдет по времени).

1

@v0dka

Был в последнее время занят сильно, не успел порешать))) скоро попробую и если что отпишу)

0