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

Question

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

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

Вот мой код компилировать:

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

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 < G->rows; i++) 
     for(j = 0; j < G->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 < 0 || neighbor.row >= G->rows || neighbor.col < 0 || 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 < rows; i++) 
     G->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 < G->rows; i++){ 
      for(j = 0; j < G->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 < G->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:

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

Answer 1

Обновление.

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

Исправления в функции 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|***********| 
|-------------------| 

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