Решение лабиринта с помощью DFS

В школьном проекте нам нужно было решить лабиринт, заданный параметром программы. Для этого нам нужно использовать алгоритм поиска в глубину.

Мне удалось найти псевдокод алгоритма DFS и даже перекодировать его с помощью C. Алгоритм способен найти выход, однако сейчас я ищу способ получить путь от начала до конца лабиринт.

Начало каждого лабиринта — левый верхний угол, а конец — правый нижний угол.

Начальный лабиринт (X = Стены; * = Свободное пространство):

*****XX****X********XXXX
XX******XX***XXXXX***XXX
XX***XXXX**XXXXX****XXXX
XX***XXXXXXXXXXXXXX****X
*****XXXXXX****XX***XXXX
XX*************XXXX*****

Решенный лабиринт (o = путь от начала до конца):

oooooXXooooXooooooooXXXX
XX**ooooXXoooXXXXX*o*XXX
XX***XXXX**XXXXX***oXXXX
XX***XXXXXXXXXXXXXXo***X
*****XXXXXX****XX**oXXXX
XX*************XXXXooooo

Вот код, который я смог создать до сих пор:

#include "../include/depth.h"

static t_bool   stack_push(t_list **stack, int x, int y)
{
  t_cell    *cell;

  if (!(cell = malloc(sizeof(t_cell))))
    return (FALSE);
  cell->coord.x = x;
  cell->coord.y = y;
  if (!my_list_push(stack, cell))
    {
      free(cell);
      return (FALSE);
    }
  return (TRUE);
}

static t_bool   is_colored(const t_list *colored, int x, int y)
{
  while (colored != NULL)
    {
      if (((t_cell *) colored->elm)->coord.x == x &&
      ((t_cell *) colored->elm)->coord.y == y)
    return (TRUE);
      colored = colored->next;
    }
  return (FALSE);
}

static t_bool   push_edges(t_map *map, t_stack *stack, int x, int y)
{
  if (x - 1 >= 0 && !is_colored(stack->colored, x - 1, y))
    stack_push(&stack->stack, x - 1, y);
  if (x + 1 < map->sz.x && !is_colored(stack->colored, x + 1, y))
    stack_push(&stack->stack, x + 1, y);
  if (y - 1 >= 0 && !is_colored(stack->colored, x, y - 1))
    stack_push(&stack->stack, x, y - 1);
  if (y + 1 < map->sz.y && !is_colored(stack->colored, x, y +1))
    stack_push(&stack->stack, x, y + 1);
  return (TRUE);
}

static t_bool   exit_properly(t_stack *stack, void *curr)
{
  my_list_destroy(&stack->stack, LIST_FREE_PTR, NULL);
  my_list_destroy(&stack->colored, LIST_FREE_PTR, NULL);
  free(curr);
  return (TRUE);
}

t_bool      depth(t_map *map)
{
  t_stack   stack;
  t_cell    *curr;

  stack.colored = stack.stack = NULL;
  stack_push(&stack.stack, MAP_START_X, MAP_START_Y);
  while (stack.stack != NULL)
    {
      curr = stack.stack->elm;
      my_list_pop(&stack.stack, &stack.stack);
      if (curr->coord.x == map->sz.x - 1 &&
      curr->coord.y == map->sz.y - 1)
    return (exit_properly(&stack, curr));
      if (!is_colored(stack.colored, curr->coord.x, curr->coord.y))
    {
      stack_push(&stack.colored, curr->coord.x, curr->coord.y);
      push_edges(map, &stack, curr->coord.x, curr->coord.y);
    }
      free(curr);
    }
  return (TRUE);
}

Первоначальный алгоритм:

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5          v = S.pop()
6          if v is not labeled as discovered:
7              label v as discovered
8              for all edges from v to w in G.adjacentEdges(v) do 
9                  S.push(w)

Спасибо.

Примечание. Типы t_list содержат общий связанный список.


c depth-first-search
person Ra'Jiska    schedule 13.05.2017    source источник
comment
Когда вы достигнете цели, все узлы, которые вы посетили по пути, должны оказаться в стеке. Просто потяните их один за другим, а затем верните список в обратном порядке.   -  person r3mainer    schedule 13.05.2017
comment
К сожалению, нет, как указано в строке псевдокода 5, элемент извлекается из стека. В списке остался только последний элемент, содержащий конец лабиринта.   -  person Ra'Jiska    schedule 13.05.2017

Ответы (1)


arrow_upward
1
arrow_downward

Предполагая, что ваши входные данные представлены в виде матрицы:

Создайте структуру со следующим определением

struct parent {
    int x, y;
};

Создайте двумерную матрицу с указанной выше структурой в качестве типа данных и с теми же размерами, что и у входной матрицы.

struct parent ** parent_info = (struct parent **)malloc(ROW_SIZE * sizeof(struct parent* ));
int i = 0;
for (i = 0; i < ROW_SIZE; i++) {
    parent_info[i] = (struct parent *)malloc(COLUMN_SIZE * sizeof(struct parent));
}

где ROW)_SIZE и COLUMN_SIZE — количество строк и столбцов соответственно в вашей входной матрице.

Теперь каждый раз, когда вы добавляете новый узел графа (ячейку матрицы) в свой стек (строка псевдокода 9), устанавливайте детали родителя в матрице parent_info (например, в псевдокоде установите «v» в качестве родителя «w»).

Например, вы переходите от (0,0) к (0,1), затем устанавливаете

parent_info[0][1].x = 0;
parent_info[0][1].y = 0;

Наконец, чтобы получить путь, рекурсивно следуйте координатам в матрице parent_info, начиная с родительских координат конечной точки лабиринта.

person Ashish kulkarni    schedule 13.05.2017