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

202
21 сентября 2017, 17:48

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

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?

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

Answer 1

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

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

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

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

  2. Проверяем соседние клетки, и если можем войти в них, входим рекурсивно.

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

READ ALSO
Модальное окно! [требует правки]

Модальное окно! [требует правки]

вопрос по модальном окне! ситуация: допустим я вошла на сайт и выбило модальное окно, я его закрыла и перешла на следующую страницу !! после...

177
document.onmouseup = null

document.onmouseup = null

примерно так выглядит обработчик для Drag'n'Drop'аОн работает

181
Конвертировать дату в другой формат

Конвертировать дату в другой формат

Как конвертировать дату в формате YYYY-MM-DD[T]HH:mm:ssSSS[Z] (например 2017-09-21T21:00:00

198
Как повесить обработчик change для метода класса

Как повесить обработчик change для метода класса

Добрый вечер, столкнулся с проблемой привязки обработчика change/click для метода sumMethod класса Create в ECMAScript 6Примерный псевдокод проблемы:

174