Поиск в глубину для матрицы

#javascript #алгоритм

Здравствуйте. У меня есть матрица вида:

matrix = [
    [0, 1, 0, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0]
 ];


Мне надо найти путь от точки start до точки end. Двигаться можно только по ячейкам,
которые содержат 0.

var start = [0,4];
 var end = [4,0];


Передвигаться я могу только в четырех направлениях. Вверх, вниз, лево, право. Направления
записаны у меня в массиве.

var direction = [[1,0], [0,1], [-1, 0], [0,-1]];


Я вроде как поняла алгоритм поиска вглубь. Но у меня проблема именно с направлениями
движения.
Вот то как поняла я:
1) устанавливаем ячейку в координаты старта.
2) начинаем сдвигать ячейку по массиву направлений.
3) если данное направление мне не подходит(ячейка равна единице или ячейки не существует,
или индексы ячейки больше размерности матрицы, или меньше нуля) возвращаюсь обратно
и перехожу на новое направление.
4) если ячейка мне походит, устанавливаю текущую ячейку в нее и вызываю функцию снова.

Только вот проблема в том, как мне проверить, а не равна ли соседняя ячейка значению
end? Просто дописать еще один if? 

Вообщем, я не совсем понимаю, как правильно реализовать сам алгоритм. Возможно как
раз алгоритм я не совсем и поняла. Буду рада любой помощи.
    

Ответы

Ответ 1

DFS у вас вероятно рекурсивный, поэтому пример сделаю для него. Для нерекурсивного
DFS логика будет похожей.

Вы говорите, нужно дойти от start до end.
Так вот, вовсе не обязательно проверять является ли эта соседняя клетка конечной.

Проще сделать немного по-другому:


Проверяем в конце ли мы, если да, то завершаем рекурсию и делаем с этими данными
что Вам нужно. Если нет, продолжаем.
Проверяем соседние клетки, и если можем войти в них, входим рекурсивно.


Таким образом, каждая клетка в которую вы войдёте, будет проверена.
Также вы избавляетесь от лишних проверок.