能否用树结构的链表和李氏算法快速解迷宫？

Question

对于大学作业，我必须尽快解决迷宫问题。使用 Lee 算法的正常实现并不难实现。

像这样的迷宫：

现在我想通过将最短路径保存在链表中来消除回溯（迭代搜索下一个最低节点）的需要。

我想如果我有一棵树，迷宫中的每个节点都连接到它相邻的每个节点。当我找到目标时，我可以遍历父连接以找到最短路线。

这是我在视觉上想象的样子：

我写了下面的代码来尝试实现这个：

//Define node struct//
struct node
{
   int i;
   int y, x;
   struct node *parent, *child;
};
//Define node struct//
 
void CreateNode(struct node *head, int x, int y, int i)
{
    struct node *new, *el; //Instantiate new node and iterating node
    new=malloc(sizeof(struct node)); //Assign memory
    new->y = y; new->x = x; new->i = i; //Assign data
    new->child=NULL;
    el=head; //Iterate from head
   
   while(el->child != NULL)
   {
      if((el->x == x + 1 || el->x == x - 1 || el->y == y + 1 || el->y == y -1) && el->i == i + 2) //check wether node is adjacent
      {
         new->parent = el; //create 'tree' parent connection if node is adjacent
         break;
      }
   }
   

   el = head; 
   while(el->child != NULL)
   {
      el = el->child; //Add new element as last element in linear linked list
   }
   el->child = new;
}

void LinkedLee(int obstructions, int xObstructPos[], int yObstructPos[], int xStartPos, int yStartPos, int xTargetPos, int yTargetPos){
   
   //Instantiate head & last node//
   struct node *head = malloc(sizeof(struct node)); 
   head->x = xTargetPos;
   head->y = yTargetPos;
   head->i = 1;
   head->child = NULL;
   head->parent = NULL;

   struct node *last = malloc(sizeof(struct node));
   last = head;
   //Instantiate head & last node//

   int i = 1;
   int x, y = 0;
   field[xTargetPos][yTargetPos] = i;

   for(int i = 0; i < obstructions; i++) //Place obstructions
   {
      field[xObstructPos[i]][yObstructPos[i]] = -1; //-1 represents obstructions in the field matrix
   }

   while(field[xStartPos][yStartPos] == 0){
      for(y=0; y<13; y++) {
         for(x=0; x<13; x++) {
            if(field[x][y] == i){ //Check if this coords adjacent to this coord can be taken
               if(field[x + 1][y] == 0 && x != 12)
               {
                  field[x + 1][y] = i + 1;
                  if(i % 2) //Check if coordinate is a node or an edge (all nodes are uneven)
                  {
                     CreateNode(head, ((x + 1)/2 - 1), (y/2 - 1), i); //Create node
                     last = last->child;
                     printf("created node");
                  }
               }

               if(field[x - 1][y] == 0 && x != 0)
               {
                  field[x - 1][y] = i + 1;
                  if(i % 2)
                  {
                     CreateNode(head, ((x + 1)/2 - 1), (y/2 -1), i);
                     last = last->child;
                     printf("created node");
                  }
               }

               if(field[x][y + 1] == 0 && y != 12)
               {
                  field[x][y + 1] = i + 1;
                  if(i % 2)
                  {
                     CreateNode(head, (x/2 - 1), ((y + 1)/2 -1), i);
                     last = last->child;
                     printf("created node");
                  }
               }

               if(field[x][y - 1] == 0 && y != 0)
               {
                  field[x][y - 1] = i + 1;
                  if(i % 2)
                  {
                     CreateNode(head, (x/2 - 1), ((y - 1)/2 - 1), i);
                     last = last->child;
                     printf("created node");
                  }
               }
            }
         }
      }
      i++;
   }
}

当我实现这个时，我遇到了分段错误，老实说，我目前还不完全理解。我希望这里有人可以帮助我理解这个想法是否可行以及为什么我的实现不起作用。

最小可复制示例

我写了一个最小的可复制示例（尽我所能）。它执行并允许您在终端中查看结果。这是我以前制作的简单迷宫：

（对于“字段”，我使用字段/迷宫坐标，因为它们更容易让人记住，我需要在这个项目的后面使用它们。）

可重现示例的代码是：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

//Define node struct//
struct node
{
  int i;
  int y, x;
  struct node *parent, *child;
};
//Define node struct//

//Instantiate functions
void CreateField(); //Fill field matrix
void PrintField(); //Print field matrix
void CreateNode(struct node *head, struct node *last, int x, int y, int i); //Create a path node
void LinkedLee(int obstructions, int obstructPos[9][2], int startTerminal, int targetTerminal);
void TerminalToCoord(int terminal, int * terminalPos); //Translate terminals to pointers to matrix coordinates
int FieldCoordToCoord(int fieldCoord); //Translate maze coordinates to matrix coordinates
int CoordToFieldCoord(int coord); //Translate matrix coordinates to maze coordinates
//Instantiate functions

int size = 9; //Instantiate with size 9;
int field[9][9] = { {-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1},
                   {-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1},
                   {-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1} }; //Instantiate Field with size 9;
int path[15][2]; //Instantiate array to store path;
int obstructPos[9][2] = {{0,0}}; //Instantiate array with positions of obstructions in field coords

int main() {
   CreateField();
   LinkedLee(1, obstructPos, 1, 4);
   PrintField();
   return 0;
}

void CreateField()
{
  int x, y;
  for(y=0; y < size; y++) 
   {
       for(x=0; x < size; x++) 
       {
           if(x == 4 || y == 4)
           {
               field[x][y] = 0;
           }
           if(((x < 7 && x > 1) && (y == 2 || y == 6)) || ((y < 7 && y > 1) && (x == 2 || x == 6)))
           {
               field[x][y] = 0;
           }
       }
   }
}

void PrintField()
{
  int x, y;
   for(y=0; y < size; y++) {
     for(x=0; x < size; x++) {
        if(field[x][y] == -1)
        {
           printf("\033[0;31m"); //Print in red
        } else {
           printf("\033[0;32m"); //Print in green
        }

        printf("%d",field[x][y]); printf("\t"); //Print the value of current coord
     }
     printf("\033[0;37m%d\t", y); //print y-axis label in white
     printf("\n\v");
  }

  for(int i = 0; i < size; i ++){
     printf("\033[0;37m%d\t", i); //Print x-axis label
  }
  printf("\033[0;37m\n\n\n"); //print 3 newlines & print in white
}

void LinkedLee(int obstructions, int obstructPos[9][2], int startTerminal, int targetTerminal)
{
   //Instantiate function variables
   int distanceFromTarget = 1;
   int x, y = 0;

   //Translate terminals into target & start coordinates
   int * targetPos; targetPos = (int *) malloc(2*sizeof(int));
   int * startPos ; startPos = (int *) malloc(2*sizeof(int));
   TerminalToCoord(startTerminal, startPos); //Get coords of start terminal (*startPos, *(startPos + 1))
   TerminalToCoord(targetTerminal, targetPos); //Get coord of target terminal (*targetPos, *(targetPos + 1))

   printf("Starting with target terminal %d, stopping at start terminal %d.\n", targetTerminal, startTerminal);
   //Instantiate head & last node//
   struct node *head = malloc(sizeof(struct node)); 
   head->x = CoordToFieldCoord(*targetPos);
   head->y = CoordToFieldCoord(*(targetPos + 1));
   head->i = distanceFromTarget;
   head->child = NULL;
   head->parent = NULL;

   struct node *last = malloc(sizeof(struct node)); 
   last = head;
   //Instantiate head & last node//
   
   field[*targetPos][*(targetPos + 1)] = distanceFromTarget; //Flood target terminal

   for(int j = 0; j < obstructions; j++) //Translate obstruction field coords to coords and place obstruction
   {
       field[FieldCoordToCoord(obstructPos[j][0])][FieldCoordToCoord(obstructPos[j][1])] = -1; 
   }

   while(field[*startPos][*(startPos + 1)] == 0){                              //Until the start coord is flooded ->
       for(y=0; y < size; y++) {                                               //For every y
           for(x=0; x < size; x++) {                                           //For every x
               if(field[x][y] == distanceFromTarget){                          //Check if current coord was just flooded
                   if(field[x + 1][y] == 0 && x != 12)                         //Check if any adjacent coord is empty
                   {
                       field[x + 1][y] = distanceFromTarget + 1;
                       if(distanceFromTarget % 2)
                       {
                           CreateNode(head, last, CoordToFieldCoord(x), CoordToFieldCoord(y), distanceFromTarget);
                           printf("created node\n");
                       }
                   }
                    if(field[x - 1][y] == 0 && x != 0)                         //Check if any adjacent coord is empty
                   {
                       field[x - 1][y] = distanceFromTarget + 1;
                       if(distanceFromTarget % 2)
                       {
                           CreateNode(head, last, CoordToFieldCoord(x), CoordToFieldCoord(y), distanceFromTarget);
                           printf("created node\n");
                       }
                   }
                    if(field[x][y + 1] == 0 && y != 12)                         //Check if any adjacent coord is empty
                   {
                       field[x][y + 1] = distanceFromTarget + 1;
                       if(distanceFromTarget % 2)
                       {
                           CreateNode(head, last, CoordToFieldCoord(x), CoordToFieldCoord(y), distanceFromTarget);
                           printf("created node\n");
                       }
                   }
                    if(field[x][y - 1] == 0 && y != 0)                         //Check if any adjacent coord is empty
                   {
                       field[x][y - 1] = distanceFromTarget + 1;
                       if(distanceFromTarget % 2)
                       {
                           CreateNode(head, last, CoordToFieldCoord(x), CoordToFieldCoord(y), distanceFromTarget);
                           printf("created node\n");
                       }
                   }
               }
           }
       }
       distanceFromTarget++;
   }

   free(targetPos);
   free(startPos);
}

void CreateNode(struct node *head, struct node *last ,int x, int y, int i)
{
   struct node *new, *el; //Instantiate new node and iterating node
   new=malloc(sizeof(struct node)); //Assign memory
   new->y = y; new->x = x; new->i = i; //Assign data
   new->child=NULL;
   el=head; //Iterate from head
  
   if(el->child = NULL)
   {
       new->parent = el;
   } else {
       while(el->child != NULL)
       {
           int elPlace = FieldCoordToCoord(el->child->x) + FieldCoordToCoord(el->child->y);
           int newPlace = FieldCoordToCoord(x) + FieldCoordToCoord(y);
           if((newPlace + 1 == elPlace || newPlace - 1 == elPlace) && el->child->i == i + 2) //check wether node is adjacent
           {
               new->parent = el; // 
               break;
           }
       }
   }

   last->child = new;
   last = last->child;

   printf("Flooded new node c%d%d, with distance: %d\n", y,x,i);
}

void TerminalToCoord(int terminal, int * terminalPos)
{
   //Translate terminal into coordinates//
   switch(terminal)
   {
       case 1:
           *terminalPos = 4;
           *(terminalPos + 1) = 8;
           break;
       case 2:
           *terminalPos = 8;
           *(terminalPos + 1) = 4;
           break;
       case 3:
           *terminalPos = 4;
           *(terminalPos + 1) = 0;
           break;
       case 4:
           *terminalPos = 0;
           *(terminalPos + 1) = 4;
           break;
       default:
           printf("%d is not a valid terminal value. Please enter a valid terminal.", terminal);
           break;
   }
}

int CoordToFieldCoord(int coord)
{
   int fieldCoord;
   fieldCoord = (coord/2 -1);
   return fieldCoord;
}

int FieldCoordToCoord(int fieldCoord)
{
   int coord;
   coord = (fieldCoord*2 + 1);
   return coord;
}

很长，但我无法举出更短的例子。它执行但实际上并未完成任务。我知道这个问题是否太复杂以至于任何人都无法提供帮助。虽然，我希望有人比我更了解这个问题。

Answer 1

这里有几个问题，包括：

• x != 12

  状态不佳；它应该是

  x < size

  并且应该使用x作为索引进行测试

  before

  。类似的错误发生在类似的

  if

  条件下。这些错误可能会导致未定义的行为，例如分段错误。

• 在

  CreateNode

  中，如果

  while

  循环进入，永远不会退出，因为循环条件永远不会改变。

  el

  永远不会改变，所以链表上也没有迭代；

  el

  永远只等于

  head

  .

• 在

  CreateNode

  中，我看不出

  newPlace

  的计算有何意义：它添加了x和y坐标，但这并不是唯一定义一个“地方”。有一个完整的位置对角线共享相同的 x 和 y 坐标之和。

您可以用更简单的方式实现链表的想法：创建一个二维数组

comeFrom

（

goTo

——无论你怎么看），很像

field

，但它存储坐标（很像

path 

).然后，当您访问一个单元格时，将您在广度优先搜索中来自何处的坐标存储在

comeFrom

中的相应条目中。通过这种方式，您可以在字段的每个访问单元格中构建一个隐式链表。

然后继续根据该信息构建路径。

我调整了你的代码来实现这个想法。请注意，我删除了障碍物的概念，因为我将它们直接编码在

field

定义中——它与您的问题无关：

#include <stdio.h>
#include <stdlib.h>

struct node {
  int i;
  int y, x;
  struct node *parent, *child;
};

int size = 9;
int field[][9] = { {-1,-1,-1,-1, 0,-1,-1,-1,-1},
                    {-1,-1,-1,-1, 0,-1,-1,-1,-1},
                    {-1,-1, 0, 0, 0, 0, 0,-1,-1},
                    {-1,-1, 0,-1, 0,-1, 0,-1,-1},
                    { 0, 0, 0, 0, 0, 0, 0, 0, 0},
                    {-1,-1, 0,-1, 0,-1, 0,-1,-1},
                    {-1,-1, 0, 0, 0, 0, 0,-1,-1},
                    {-1,-1,-1,-1, 0,-1,-1,-1,-1},
                    {-1,-1,-1,-1, 0,-1,-1,-1,-1}};
int path[15][2];

void printField() {
    for (int y = 0; y < size; y++) {
        for (int x = 0; x < size; x++) {
            printf("\033[0;3%dm%d\t", field[x][y] == -1 ? 1 : 2, field[x][y]); //Print in red or green
        }
        printf("\033[0;37m%d\t\n\v", y); //print y-axis label in white
    }
    for (int i = 0; i < size; i ++) {
        printf("\033[0;37m%d\t", i); //Print x-axis label
    }
    printf("\033[0;37m\n\n\n"); //print 3 newlines & print in white
}

int linkedLee(int startX, int startY, int targetX, int targetY) {
    int distanceFromTarget = 1;
    // This represents the "linked list": each cell can point to a neighbor:
    int comeFrom[size][size][2]; 
    // The four directions we can move
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};
    
    field[targetY][targetX] = distanceFromTarget;
    while (1) {
        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                if (field[y][x] == distanceFromTarget) {
                    if (x == startX && y == startY) { // bingo!
                        // Build path from comeFrom (linked list)
                        path[0][0] = x;
                        path[0][1] = y;
                        int i = 1;
                        while (x != targetX || y != targetY) {
                            int *pair = comeFrom[y][x];
                            x = path[i][0] = pair[0];
                            y = path[i][1] = pair[1];
                            i++;
                        }
                        return i;
                    }
                    for (int dir = 0; dir < 4; dir++) {
                        int x1 = x + dx[dir];
                        int y1 = y + dy[dir];
                        if (y1 >= 0 && x1 >= 0 && y1 < size && x1 < size && field[y1][x1] == 0) { 
                            // field is available and not visited yet
                            field[y1][x1] = distanceFromTarget + 1;
                            comeFrom[y1][x1][0] = x;
                            comeFrom[y1][x1][1] = y;
                        }
                    }
                }
            }
        }
        distanceFromTarget++;
    }
}

void printPath(int pathSize) {
    for (int i = 0; i < pathSize; i++) {
        printf("(%d,%d) ", path[i][0], path[i][1]);
    }
    printf("\n");
}

int main() {
    int pathSize = linkedLee(0, 4, 4, 0);
    printField();
    printPath(pathSize);
    return 0;
}