如何打印从源的BFS路径,目标在迷宫 [英] How to print the BFS path from a source to a target in a maze
问题描述
我想实现BFS,以便找到一个目标源在迷宫最短路径。
I'm trying to implement the BFS in order to find the shortest path from a source to a target in a maze.
这是我遇到的问题是,我无法打印的路径,它是在迷宫中印有*,但我怎么能提取从BFS的predecessors不打印路径所有的访问节点?
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?
下面是我的code为您编译:
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:
我怎么能只打印的最短路径?而为什么'T'前的空格没有它有一个*?
预先感谢您所有的时间。
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.
推荐答案
UPD。
我纠正我的code和你一点点。您需要 preD
数组不是数组,但的矩阵大小[G-&GT;行] [G-&GT;西]
。从什么电池你来到这个矩阵显示的每一个细胞!我想你明白这个想法不正确,你填写 preD
以线性的方式排列,这是无谓的。但我不希望太多改变你的接口,所以我用 preD
为线性阵列,但实际上它是矩阵。
I corrected my code and yours a little bit. You need pred
array not as array, but as matrix size of [G->rows][G->col]
. Every cell of this matrix show from what cell you came! I think that you understand this idea incorrectly, you fill pred
array in linear way, that is senselessly. But I don't want to change your interfaces much, so I use pred
as linear array, but actually it is matrix.
在BFSPathMatrix功能更正:
Corrections in BFSPathMatrix function:
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
阵列和填充细胞去源小区。
Main idea is that you should go from targed cell to source cell using your pred
array and fill cells on this path with '*' mark
这篇关于如何打印从源的BFS路径,目标在迷宫的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!