Узнайте минимальные шаги, чтобы добраться до любого угла лабиринта?

Question

Вы дали n*m лабиринт (матрица), который содержит значения 0 , 1 и 2 .значение 0 означает, что ячейка открыта, значение 1 означает, что ячейка является блоком, а значение 2 является отправной точкой.Вы можете идти только в левом, правом, верхнем, нижнем направлении в лабиринте.Найти минимальное расстояние от начальной точки до любого угла матрицы.

Пример:
n = 4, m = 5
лабиринт:

1 1 1 0 1
1 0 2 0 1
1 0 1 0 1
0 0 1 0 1

Ответ будет 2.
path ->отправная точка (2 ,3)->(2,4)->(1,4).

Помогите мне решить эту проблему !!

Answer 1

Если вы знакомы с BFS и уже решили следующую классическую задачу:

Рассчитайте кратчайший путь от начальной точки до конечной точки в 2D-сетке с некоторыми препятствиями!

тогда вы можете решить свою проблему, запустив BFS из начальной точки, а затем пройдя все угловые точки, имеющие значение 0, и сравнив минимальное расстояние между ними.

Там может бытьнесколько дорожек, ведущих к минимальному расстоянию.Если вы хотите отследить путь, тогда вы можете сохранить другую сетку 2D для хранения информации родителя о каждой 2D точке при выполнении BFS.

Пожалуйста, дайте мне знать, если у вас возникнут проблемыпока кодирую.Спасибо !!