Как печатать путь BFS от источника до цели в лабиринте

Я пытаюсь реализовать BFS, чтобы найти кратчайший путь от источника до цели в лабиринте.

Проблема, с которой я столкнулась, заключается в том, что я не могу напечатать путь, он напечатан с помощью «*» в лабиринте, но как я могу извлечь путь из предшественников BFS без печати всех посещенных узлов?

Вот мой код для компиляции:

#include  #include  #include  struct coord{ //This is a struct I'll use to store coordinates int row; int col; }; //---------QUEUE.C-------// struct TQueue{ struct coord *A; int QUEUE_MAX; }; typedef struct TQueue *Queue; Queue initQueue(int size){ // Initialize the queue Queue Q = malloc(sizeof(struct TQueue)); Q->A = malloc(size*sizeof(struct coord)); Q->QUEUE_MAX = size+1; Q->A[0].row = 0; //I'll use only the row value for first and last element Q->A[Q->QUEUE_MAX].row = 1; return Q; } int emptyQueue(Queue Q){ return Q->A[0].row == 0; } int fullQueue(Queue Q){ return Q->A[0].row == Q->A[Q->QUEUE_MAX].row; } void enqueue(Queue Q, struct coord value){ if(!fullQueue(Q)){ Q->A[Q->A[Q->QUEUE_MAX].row] = value; // Insert in tail if(emptyQueue(Q)){ Q->A[0].row = 1; // If is empty, the head will be in the first position } Q->A[Q->QUEUE_MAX].row = (Q->A[Q->QUEUE_MAX].row%(Q->QUEUE_MAX - 1)) + 1; } else{ puts("Coda piena"); } } struct coord dequeue(Queue Q){ struct coord value; if(!emptyQueue(Q)){ value = Q->A[Q->A[0].row]; // I take the "head" value Q->A[0].row = (Q->A[0].row%(Q->QUEUE_MAX - 1)) + 1; if(fullQueue(Q)){ Q->A[0].row = 0; Q->A[Q->QUEUE_MAX].row = 1; } } else{ puts("Coda piena"); } return value; } //------------GRAPH.C-------- struct TGraph{ char **nodes; int rows; int cols; struct coord S; struct coord T; }; typedef struct TGraph *Graph; enum color{ WHITE, GREY, BLACK // I will use these for undiscovered, unvisited and visited nodes }; int BFSPathMatrix(Graph G, struct coord *pred){ int i, j; struct coord neighbor, source = G->S; //I use "source" in order to move in the maze and neighbor for visiting the adiacents enum color visited[G->rows][G->cols]; for(i = 0; i rows; i++) for(j = 0; j cols; j++) visited[i][j] = WHITE; //Undiscovered Queue coda = initQueue(G->rows*G->cols); visited[G->S.row][G->S.col] = GREY; //Discovered enqueue(coda, source); i = 0; while(!emptyQueue(coda)){ source = dequeue(coda); int moves[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; //I can move right, left, down and up for(j = 0; j < 4; j++){ neighbor.row = source.row + moves[j][0]; neighbor.col = source.col + moves[j][1]; if(neighbor.row = G->rows || neighbor.col = G->cols) continue; if(neighbor.row == G->T.row && neighbor.col == G->T.col){ pred[i++] = G->T; //G->nodes[source.row][source.col] = '*'; free(coda); return 1; } if(visited[neighbor.row][neighbor.col] == WHITE && G->nodes[neighbor.row][neighbor.col] == ' '){ //If it's undiscovered, we put it in the queue pred[i++] = source; //G->nodes[source.row][source.col] = '*'; visited[neighbor.row][neighbor.col] = GREY; enqueue(coda, neighbor); } } } free(coda); return -1; } Graph initGraphMatrix(int rows, int cols){ int i; Graph G = malloc(sizeof(struct TGraph)); G->nodes = malloc(rows*sizeof(char *)); for(i = 0; i nodes[i] = malloc(cols*sizeof(char)); G->rows = rows; G->cols = cols; return G; } void printGraphMatrix(Graph G){ if(G != NULL){ int i, j; for(i = 0; i rows; i++){ for(j = 0; j cols; j++) putchar(G->nodes[i][j]); putchar('\n'); } } } int main(){ Graph G = initGraphMatrix(11, 21); G->S.row = 1; G->S.col = 1; G->T.row = 9; G->T.col = 7; strcpy(G->nodes[0], "|-------------------|"); strcpy(G->nodes[1], "|S | | |"); strcpy(G->nodes[2], "| |-| |-| |---| | | |"); strcpy(G->nodes[3], "| | | | | | |"); strcpy(G->nodes[4], "| | |---| | |---| | |"); strcpy(G->nodes[5], "| | | | | | | | |"); strcpy(G->nodes[6], "| | | | |-| | | | | |"); strcpy(G->nodes[7], "| | | | | | | |"); strcpy(G->nodes[8], "| | | |-| |-------| |"); strcpy(G->nodes[9], "| | T| |"); strcpy(G->nodes[10], "|-------------------|"); struct coord pred[(G->rows*G->cols)]; printGraphMatrix(G); system("PAUSE"); if(BFSPathMatrix(G, pred) != -1){ int i; for(i = 0; i rows*G->cols; i++){ if(pred[i].row == G->S.row && pred[i].col == G->S.col) continue; if(pred[i].row == G->T.row && pred[i].col == G->T.col) break; G->nodes[pred[i].row][pred[i].col] = '*'; } printGraphMatrix(G); }else puts("Target unreachable"); system("PAUSE"); return 0; } 

Так выглядит лабиринт до и после BFS: Bad_maze

Как напечатать только кратчайший путь? И почему пространство до ‘T’ не имеет в нем ‘*’? Спасибо заранее за все ваше время.

Upd.

Я исправил свой код и ваш немного. Вам нужен массив pred не как массив, а как размер матрицы [G->rows][G->col] . Каждая ячейка этой матрицы показывает, из какой ячейки вы пришли! Я думаю, что вы неправильно понимаете эту идею, вы заполняете массив pred линейным способом, то есть бессмысленно. Но я не хочу сильно менять свои интерфейсы, поэтому я использую pred как линейный массив, но на самом деле это matrix.

Исправления в функции BFSPathMatrix:

  if(neighbor.row == G->T.row && neighbor.col == G->T.col){ pred[neighbor.row*G->cols + neighbor.col] = source; free(coda); return 1; } if(visited[neighbor.row][neighbor.col] == WHITE && G->nodes[neighbor.row][neighbor.col] == ' '){ //If it's undiscovered, we put it in the queue pred[neighbor.row*G->cols + neighbor.col] = source; visited[neighbor.row][neighbor.col] = GREY; enqueue(coda, neighbor); } 

Исправления в основной функции:

 if(BFSPathMatrix(G, pred) != -1){ struct coord T = G->T; int predInd = T.row*G->cols + T.col; while (pred[predInd].row != G->S.row || pred[predInd].col != G->S.col) { predInd = T.row*G->cols + T.col; T = pred[predInd]; if( G->nodes[T.row][T.col] == ' ') G->nodes[T.row][T.col] = '*'; } printGraphMatrix(G); }else puts("Target unreachable"); 

результат:

 |-------------------| |S | | | | |-| |-| |---| | | | | | | | | | | | | |---| | |---| | | | | | | | | | | | | | | | |-| | | | | | | | | | | | | | | | | |-| |-------| | | | T| | |-------------------| Press any key to continue . . . |-------------------| |S**** |*******|***| | |-|*|-|*|---|*|*|*| | | |*****|*****|*|*| | | |---| |*|---|*|*| | | |***| |***| |*|*| | | |*|*|-| |*| |*|*| | | |*|***| |*****|*| | | |*|-|*|-------|*| | |**T|***********| |-------------------| 

Основная идея заключается в том, что вы должны перейти от привязанной ячейки к исходной ячейке с помощью вашего массива pred и заполнить ячейки на этом пути знаком «*»