我有一个迷宫程序，它接收5个迷宫并将节点插入到这些迷宫的轮廓中。我正在创建一个有向图，它可以通过在每个自由空间网格位置放置一个图节点并将它们与边连接在一起来表示迷宫中的自由空间。

我被困在一个函数上，该函数实际上涉及用节点填充迷宫的自由空间并连接它们。目前，节点不需要遵循特定的模式，它们仅需要填充所有空白空间，如下图所示。我的程序现在只显示一个没有节点的空白迷宫。

我在computeGraph()中给出了一组指导原则，但我对如何递归地跟踪迷宫感到非常困惑。我在该函数下的代码是乱码，什么也不做。我真的不知道该怎么办，希望能得到一些帮助或指导。我不要求触摸程序中的任何其他内容，仅要求computeGraph()，因为这是我现在的问题。另外我还要指出，不允许我为此任务创建任何额外的数组，这会使问题更加棘手。

如果注释不够，基本上该函数的目的是为新图形分配空间并返回它。图的每个节点必须通过设置适当的节点上/下/左/右指针来动态分配和连接。

再次感谢您的帮助。如果需要，我可以发布程序的完整代码/所有文件，但是我只发布了我认为对这个特定问题必要的内容。

maze.c：

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

#include "graphSet.h"
#include "mazeDisplay.h"

// Compute the graph for the given maze and add it to the given graph set.
Graph *computeGraph(char maze[HEIGHT][WIDTH]) {

  // Create the initially-empty graph
  int i,j;
  for(i = 0; i < HEIGHT; i++){
    for(j = 0; j < WIDTH; j++){
      maze[i][j] = '\0';
    }
  }

  // Find a starting node,then trace out the maze recursively.  A starting node can be
  // found by searching from top to bottom,left to right,for a non-wall maze location.
  // You MUST NOT hard-code this start location ... it must be determined by your code.

  Node *newNode;
  Node *currNode;
  Node *prevNode;

  currNode = *rootNode;
  currPos[0][0];
  prevNode = NULL;
  while(currNode != NULL){
    if(currPos[0][0] == maze[x][y]){
      break;

    }

    prevNode = currNode;
  }


  newNode = malloc(sizeof(Node));
  if(prevNode->up != 1){
    prevNode->up = newNode;
  }else if(prevNode->down != 1){ 
    prevNode->down = newNode;
  }else if(prevNode->left != 1){ 
    prevNode->left = newNode;
  }else if(prevNode->right != 1){
    prevNode->right = newNode;
  }

  // To trace out the maze recursively,you will likely want to create a recursive
  // procedure that is called by this one.   It should take parameters to indicate
  // the location in the maze to start tracing from,the maze itself and also the node
  // that led to this node (i.e.,the previous one in the tree that led here).  If you
  // start with the root node,then the previous node should be NULL.
  //
  // As you go through the maze,make sure to mark off maze locations that you have
  // visited (perhaps by putting a '2' character at that location) so that you do not
  // go back to that location again and end up with infinite recursion.  So you can
  // stop the recursion when you reach a wall (i.e.,a '1' character in the maze) or a
  // '2' character.  A '0' character means that it is a free space that you just arrived
  // at for the first time.   Make sure to check recursively in all directions.  In my
  // solutions (shown on the assignment),I used an ordering of up/down/left/right.  So
  // if you want solutions to look like mine,you should follow that ordering as well.
  //
  // As you traverse the maze,make sure to connect the previous node to the current one.
  // You'll have to check which direction you can from (i.e.,x and y values) so that
  // you know whether it is the up/down/left or right pointer to set.

}



// This procedure must clean up graph by removing all nodes in which the previous and
// next nodes have the same x or y value as it.
void cleanUpGraph(Node *n,Node *previousnode) {

}



// This is where it all begins
int main() {
  char mazes[5][HEIGHT][WIDTH] = {
    {"111111111111111111111","100000001000100000001","101111111010111011111","100000000010000010001","101110111111101110111","100010001000000000001","111011111111111110111","101010001000100000001","101110111011101011101","100010000000001010001","101010111011111111111","101000001000100000001","101111111110101111101","100010100000100000101","111110101110101111101","100010001000000010101","101010111111111010111","101010001000000010001","101111111010111011101","100000000010001000001","111111111111111111111"},{"111111111111111111111","100000000000000000001","101111111111111111111","111111111111111111101","101111111111111111101","101000100010001000101","101010101010101010101","100010001000100010001","101110111011101110111","101111101111101111101","101111111001111111101","100111111111111111001","100011111111111110001","100001111111111100001","100000111111111000001","100000011111110000001","100000001111100000001","100000000111000000001","100000000010000000001","111111111111111111111","111111111110111111111","111100000000000000001","111000000000000000001","111111111111111111111"}};

  // Open a display window
  openDisplayWindow();



  // Allocate a GraphSet to store the graphs for each maze
  GraphSet *gSet;

  // Compute the graphs for each maze and add them to a Graph Set
  for (int i=0; i<5; i++) {
    Graph *g = computeGraph(mazes[i]);

    // Add g to gSet properly
    // ...
  }

  // Show the graphs
  Graph *g; // ... set this to the first graph in gSet ...

  for (int i=0; i<5; i++) {
    drawMaze(mazes[i]);  // Draw the maze
    // drawGraph(g->rootNode);    // Draw the graph

    getchar();  // Wait for user to press enter

    // cleanUpGraph(g->rootNode,NULL);   // Clean up the graph
    // drawMaze(mazes[i]);
    // drawGraph(g->rootNode);

    // ... get the next graph in the set ...
    // ... INSERT A LINE OF CODE HERE ...

    getchar();  // Wait again for the user to press ENTER before going on to the next maze
  }

  // Free up all allocated memory
  // ...

  // Close the display window
  closeDisplayWindow();
}

graphSet.h：

// This struct represents a single intersection/Node in a maze.  It keeps track
// of the x(i.e.,column) and y (i.e. row) of the intersection in the maze
// as well as the Nodes in all 4 directions around it).   NULL is used to
// indicate that no Node is beside it in a particular direction.
typedef struct nd {
  int        x;
  int        y;
  struct nd *up;
  struct nd *down;
  struct nd *left;
  struct nd *right;
} Node;


// This struct represents a single maze graph
typedef struct gr {
  Node       *rootNode;
  struct gr  *nextGraph;
} Graph;


// This struct represents a set of maze graphs
typedef struct {
  Graph  *firstGraph;
  Graph  *lastGraph;
} GraphSet;