Составить программу нахождения самого кратчайшего пути

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

Задача
По заданной карте лабиринта (размера 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

Сообщение от v0dka Добрые люди, помогите с алгоритмом

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

0

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

0

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

1

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

0

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

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

1

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

0

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

наоборот, во второй раз ей нужно уменьшать расстояние, иначе не вычислим:

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

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

1

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

0