c - 如何在迷宫中打印从源到目标的 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 数组，这是毫无意义的。但是我不想对你的接口(interface)做太多改动，所以我使用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|***********|
|-------------------|

主要思想是，您应该使用 pred 数组从目标单元格转到源单元格，并用“*”标记填充此路径上的单元格