Блог

Главная - Вопросы по программированию - Рекурсивный поиск пути в лабиринте

Рекурсивный поиск пути в лабиринте

#c #depth-first-search #maze

#c #поиск в глубину #Лабиринт

Вопрос:

Редактировать: выход из лабиринта обнаруживается только тогда, когда вдоль границ лабиринта есть пустое место без каких-либо стен.

Редактирование 2: я немного изменил код после получения справки, но все равно столкнулся с той же проблемой. Может быть, я неправильно использовал то, что было упомянуто. Я изменил фрагмент моего кода только на одну рекурсию (часть перемещения вверх), чтобы минимизировать ненужное повторение при просмотре фрагмента.

(Все еще новичок в кодировании, надеюсь, вы не возражаете) Я пытаюсь написать код для программы, которая печатает движение человека, который находит путь через данный лабиринт.

Однако я столкнулся с проблемой, когда после достижения выхода из лабиринта человек возвращается в исходное положение, в котором он находится.

Исходное положение задается координатами (x, y).

Вот фрагмент моей функции, которая находит путь через лабиринт:

 bool find_path(char **maze, long **track, long rows, long cols, long x, long y, long steps)
{
  bool found;
  if (goal_found(maze, rows, cols, x, y)) {
    return true;
  }

  track[y][x] = 2;

  if (maze[y - 1][x] == EMPTY amp;amp; track[y - 1][x] == 1) { // Move Up
    steps  ;
    found = find_path(maze, track, rows, cols, x, y - 1, steps);
    if (found) {
      return true;
    }
      steps;
  }
}

Комментарии:

1. Первое, что я замечаю, это то, что вы выполняете рекурсивные вызовы без использования true false возвращаемого значения / . Если лабиринт решен, вызывающая функция об этом не знает.

2. Возможно ли, чтобы вы уточнили это? Я не совсем понимаю, что вы имеете в виду, используя возврат true / false. Если лабиринт решен, что означает, что моя логическая функция is_goal возвращает true , тогда исходная функция search_maze также возвращает true .

3. Я имею в виду, что воплощение, которое повторило, не знает этого. search_maze(maze, track, rows, cols, x, y - 1, steps); Я предлагаю вам bool result = search_maze(maze, track, rows, cols, x, y - 1, steps); , а затем предпринять соответствующие действия. Вы не можете завершить рекурсию, не пройдя через стек вызовов, ячейку за ячейкой. Промежуточные уровни вызовов не пропускаются просто возвращением true , рекурсия работает не так.

4. запишите ваш возврат и проверьте его

5. Спасибо за совет!! Я попробовал это снова, но по какой-то причине у меня это не работает, возможно, я неправильно использовал то, что было упомянуто. Я добавил указанные изменения в свой код.

Ответ №1:

Ваша программа находит все пути в лабиринте; если вы хотите остановить это, вам нужно изменить свои вызовы, чтобы остановить прохождение лабиринта, если вы достигли успеха:

   found = search_maze(maze, track, rows, cols, x, y   1, steps);
  swap(maze, y, x, y   1, x);
  if (found) {
      return found;
  }

При всех рекурсивных вызовах.