5

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

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?

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

13
  • Вроде в вопросе всё верно и подробно описано...
    – Qwertiy
    20 сен 2017 в 15:20
  • @Qwertiy, вот только с реализацией у меня не получается. Вроде логика и правильная, а оно не работает. 20 сен 2017 в 15:29
  • 1
    @kittycat_13 Написал Вам приблизительно как это может выглядеть. Может можно сделать это проще или как-то по-другому... собственно ссылка
    – Igor Lut
    20 сен 2017 в 20:00
  • @IgorLut, спасибо большое) 21 сен 2017 в 7:28
  • @IgorLut, я написала свой вариант функции, но у меня есть несколько проблем. Во первых - при запуске скрипта мне выдается ошибка, что стек переполнен(Uncaught RangeError: Maximum call stack size exceeded) в строке, где я объявляю переменную dimension. И второе - как мне реализовать условие, что если нет пути куда двигаться. У меня как-то косо все получилось. Посмотрите, пожалуйста. jsfiddle.net/LsLLetjv 21 сен 2017 в 10:22

1 ответ 1

3

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

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

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

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

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

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

9
  • А суть самого алгоритма, как вы скорее всего и сами поняли, в рекурсивном входе в каждую подходящую вершину, чтобы в итоге по шажкам прийти в конечную :)
    – witaway
    20 сен 2017 в 20:35
  • Спасибо большое. Только один вопрос. В первом пункте мы делаем проверку на то, находимся ли мы в ячеек до которой надо дойти, то есть до end? 21 сен 2017 в 7:30
  • И еще вопрос, если можно) По второму пункту. У меня например есть две соседние клетки в которые я могу зайти. Мне заходить по очереди в обе? 21 сен 2017 в 7:32
  • Да. Именно так. Вы ставите несколько if для всех соседей (i ± 1, j±1) и проверяете, можно ли зайти в каждую из них. Если у вас получится несколько таких клеток, то вы сначала войдёте в одну из них, а потом, через некоторое время, рекурсия вернётся обратно, после чего войдёт в другую :-)
    – witaway
    21 сен 2017 в 13:25
  • А если у меня такая ситуация. Допустим я стою на ячейке. Перехожу на соседнюю ячейку. Делаю осмотр всех ближайших ячеек, но ни одна из них не подходит. Как мне сделать откат на предыдущую ячейку и поменять направление движения? 21 сен 2017 в 13:31

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.