使用 DFS 求解迷宫

Question

在一个学校项目中，我们必须解决通过程序参数给出的迷宫。为此，我们需要使用深度优先搜索算法。

我已经能够找到 DFS 算法的伪代码，甚至可以使用 C 对其进行重新编码。该算法能够找到出口，但是现在我正在寻找一种从从头到尾迷宫。

每个迷宫的起点是左上角，终点是右下角。

初始迷宫（X = 墙壁；* = 自由 Space）：

*****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 types 持有通用链表。

Answer 1

假设你的输入数据是矩阵形式：

创建具有以下定义的结构

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 矩阵中的坐标，从迷宫终点的父坐标开始。

使用 DFS 求解迷宫

Maze Solving using DFS

c

depth-first-search