如何打印从源的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;
}

这是迷宫的样子和之前的BFS后：

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屋！