Путешествие по лабиринту рекурсивно и вставка узлов во все пространства

Question

У меня есть программа-лабиринт, которая берет 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",
     "100000000000000000001",
     "101111111111111111111",
     "100000000000000000001",
     "111111111111111111101",
     "100000000000000000001",
     "101111111111111111111",
     "100000000000000000001",
     "111111111111111111101",
     "100000000000000000001",
     "101111111111111111111",
     "101111111111111111101",
     "101111111111111111101",
     "101000100010001000101",
     "101010101010101010101",
     "101010101010101010101",
     "101010101010101010101",
     "100010001000100010001",
     "111111111111111111111"},

    {"111111111111111111111",
     "100000000000000000001",
     "101010101010101010101",
     "100000000000000000001",
     "101110111011101110111",
     "100000000000000000001",
     "101111101111101111101",
     "100000000000000000001",
     "101111111001111111101",
     "100000000000000000001",
     "101111111111111111101",
     "100111111111111111001",
     "100011111111111110001",
     "100001111111111100001",
     "100000111111111000001",
     "100000011111110000001",
     "100000001111100000001",
     "100000000111000000001",
     "100000000010000000001",
     "100000000000000000001",
     "111111111111111111111"},

    {"111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111110111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111",
     "111111111111111111111"},

    {"111111111111111111111",
     "111100000000000000001",
     "111000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "100000000000000000001",
     "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;

Answer 1

Лабиринты, как показано, могут быть интерпретированы как ряд комнат с одним квадратом, которые соединяются «дверями», где бы ни касались двух пустых квадратов.
Таким образом, эта проблема упрощается для неориентированного графа идентичных комнат.
Я просто повторяю это, хотя я убежден, что вы уже пришли к такому мнению.

Следовательно, цель состоит в том, чтобы посетить каждую комнату и узнать, когда все были посещены.

Тогдацель malloc для каждого пустого пространства (но не более одного раза) может быть достигнута путем неправильного выбора только при первом посещении квадрата, что может быть гарантировано использованием флага, установленного при посещении новой комнаты, в то же время, когдаmallocing. Эти флаги можно «добавить» в каждую комнату, отразив структуру данных, в которой хранится информация о «пустой» / «стене».

Оставшаяся цель - обеспечить посещение каждого пустого квадрата до тех пор, покакак это можно посетить. Для этого я предлагаю использовать «правило левой руки» для посещения лабиринта: «Всегда выходите из комнаты через выход слева от того места, куда вы вошли». Это в основном обход ориентированных графов, аналогичный наиболее широко используемому обходу бинарных деревьев. Т.е. для возможных выходов на север, восток, юг, запад, север всегда выход через «следующий» выход в этом порядке.

Правило левой руки только для ориентированных графов без «петель» / «кругов»,конечно, НЕ применимо к вашим лабиринтам.
Чтобы решить эту проблему, используйте ветку ariadne. Это путь через все уже посещенные комнаты. Обратите внимание, что вам нужна структура данных пути, флаг для каждой комнаты недостаточен для отслеживания потока ариадны.

Если при использовании правила левой руки вы вводите комнату, которую вы уже посетили (т.е. он уже найден в пройденном вами пути), затем не вводите его и выберите следующий выход, как если бы первый выбранный выход не существовал. Представьте себе «дверь», которая будет заперта там. Когда вы выходите из не посещенных комнат, идите назад по нити ариадны, пока не найдете еще неиспользованные выходы в еще не посещенные комнаты.

Когда вас заставят вернуться в первую комнату, которую вы посетили, то выпобывали во всех комнатах.

Как описано выше, ваша ветка увеличивается при возврате во время поиска не посещенных комнат. Для более эффективной реализации вы можете сократить поток ariadne на обратном пути и полагаться на зеркальные флаги «уже заблокированы». Т.е. комната, к которой можно вернуться, находится в предыдущей записи пути, тогда как решение о том, входить в комнату, может быть основано на флаге.

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

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

Затем запрограммируйте его.