I'm trying to implement the BFS in order to find the shortest path from a source to a target in a maze.
The problem that I'm having is that I'm unable to print the path, it is printed with '*' in the maze, but how can I extract the path from the predecessors of the BFS without printing all the visited nodes?
Here's my code for you to compile:
#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;
}
This is how the maze looks like before and after the BFS:
How can I print only the shortest path? And why the space before 'T' doesn't have an '*' in it? Thanks in advance for all your time.
