logo标签列表

如何打印从起点到终点的BFS路径在迷宫中

cgraphqueuemazebreadth-first-search
4
我正在尝试实现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之前和之后迷宫的样子：Bad_maze 如何仅打印最短路径？为什么'T'前面的空格没有'*'标记？
非常感谢您的时间。
还有一些其他的 * 也缺失了（当你遇到障碍时）。 - Weather Vane
我会使用Dijkstra算法，就像我之前回答的那样(http://stackoverflow.com/questions/34256346/how-to-find-the-fastest-route-in-a-maze-in-c/34257513#34257513)。 - Weather Vane
@WeatherVane 我现在正在学习BFS，所以我想先理解它，接下来我会用同样的方法学习Dijkstra算法和A星算法。 - Aster
这只是一条评论，那里还有其他迷宫算法的链接。 - Weather Vane
@WeatherVane这非常有用，感谢您指出它们。 - Aster
1个回答
2

更新：

我对我的代码和您的代码进行了一些更改。您需要将 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|***********|
|-------------------|

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

这是您的解决方案生成的迷宫样子。我认为您的想法可能是正确的，从目标开始而不是从源开始可能更好，但我不明白您为什么要这样做：T.row*T.col - Aster
你说得对，我犯了一个错误，我已经改正了。但是你应该使用 pred 来确定单元格 pred[row][col] 的前继单元格，这是使用前继矩阵的好方法。 - valdem
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接