洪水填充算法迷宫

Question

我试图让我的程序像这样读迷宫：

    #.#######
    #.......#
    ####.####
    #....#..#
    #.####.##

并打印出迷宫中的可达区和不可达区，应该是这样的：

    #+#######
    #+++++++#
    ####+####
    #++++#--#
    #+####-##

墙用“#”表示，可通过的格子用“.”表示。

替换单元格的“+”表示可以从迷宫的顶部入口点到达这些单元格。 “-”符号是进入迷宫顶部无法到达的单元格。

例如，在上面的迷宫中，除了右下角的单元格外，所有单元格都是可达的。这是因为无法从迷宫顶部的入口点到达这些单元格。

我正在尝试使用一些递归来填充迷宫，并确定可到达的区域，但我遇到了麻烦。

这是我目前拥有的：

    int
    flood_fill(m_t * maze, int row, int col) {

        int direction;

        direction = flood_fill(maze, row+1, col); /* down */
        if (!direction) {
            direction = flood_fill(maze, row, col+1); /* right */
        }

        if (!direction) {
            direction = flood_fill(maze, row-1, col); /* up */
        }

        if (!direction) {
            direction = flood_fill(maze, row, col-1); /* left */
        }

        if (direction) {
            maze->M[row][col].type = path;
        }

        return direction;
    }

我知道我的 flood_fill 功能没有做正确的事情，我很难做到正确。任何人都可以帮助我让我的代码的洪水填充部分正确，这样我就可以在代码的其他地方调用该函数并确定可以到达哪些单元格。

Answer 1

您需要检查当前位置是路径、访问过的路径还是墙。

如果是路径，将其改为reachable and visited，然后在每个方向调用flood_fill。

如果它是一堵墙或访问过的路径，则 return 无需进一步调用 flood_fill。

在 flood_fill 完成 returned 之后，任何未访问路径的位置都无法到达。

编辑：

flood_fill 的代码可能如下所示：

void
flood_fill(m_t * maze, int row, int col) {

    if (row < 0 || col < 0 || row >= MAX_HEIGHT || col >= MAX_WIDTH) {
        /* Out of bounds */
        return;
    }
    if (maze->M[row][col].type != path_cell) {
        /* Not a path cell */
        return;
    }
    if (maze->M[row][col].visited) {
        /* We have already processed this cell */
        return;
    }

    /* We have now established that the cell is a reachable path cell */
    maze->M[row][col].visited = 1;
    maze->M[row][col].reachable = 1;
    maze->M[row][col].type = '+';  /* Not sure if you want this line or if you exchange the symbol in the presentation */

    /* Check the surrounding cells */
    flood_fill(maze, row+1, col); /* down */
    flood_fill(maze, row, col+1); /* right */
    flood_fill(maze, row-1, col); /* up */
    flood_fill(maze, row, col-1); /* left */
}

Answer 2

首先，你可以找到一个很好的迷宫递归解释here。

在您的情况下，函数应如下所示：

void
flood_fill(m_t * maze, int row, int col)
{
    // If row,col is outside maze
    if ( row < 0 || row >= maze->height || col < 0 || col >= maze->width) return;
    // If row,col is not open
    if (maze->M[row][col].type != '.') return;
    // Mark row,col as part of path.
    maze->M[row][col].type = '+';
    // Go Up
    flood_fill(maze, row, col - 1);
    // Go Right
    flood_fill(maze, row + 1, col);
    // Go Down
    flood_fill(maze, row, col + 1);
    // Go Left
    flood_fill(maze, row - 1, col);

    return;
}

使用您的示例矩阵调用此函数后的结果将是：

#+#######
#+++++++#
####+####
#++++#..#
#+####.##

在运行之后，您可以再次遍历矩阵并用 - 标记每个 . 单元格，您就完成了。

注意：调用此函数前无需更改矩阵。当你找到它时，你只需要用迷宫开始的索引调用这个函数。在您的示例中，它将是 flood_fill(maze,0,1).

Answer 3

试试这个

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_HEIGHT 100
#define MAX_WIDTH  100
#define wall '#'
#define path_cell '.'

typedef struct {
    char type;
    int reachable;
    int visited;
} mazecells_t;

typedef struct {
    int height;
    int width;
    mazecells_t M[MAX_HEIGHT][MAX_WIDTH];
} m_t;

void readmaze(m_t *maze);
void print(m_t *m);
void print_reachable(m_t *m);

int main(void) {
    m_t MAZE;

    readmaze(&MAZE);
    print(&MAZE);
    puts("");
    print_reachable(&MAZE);

    return 0;
}

void readmaze(m_t *maze) {
    int row=0, col=0;
    char ch;
    FILE *fp = stdin;//fopen("map.txt", "r");
    while(EOF != fscanf(fp, "%c", &ch)){
        if(ch == wall || ch == path_cell){
            maze->M[row][col].type = ch;
            maze->M[row][col].reachable = 0;
            maze->M[row][col].visited = 0;
            ++col;
        } else if(ch == '\n'){
            maze->width = col;
            col = 0;
            ++row;
        }
    }
    if(col != 0)
        ++row;
    //fclose(fp);
    maze->height = row;
}

void print(m_t *m){
    for(int r = 0; r < m->height; ++r){
        for(int c = 0; c < m->width; ++c){
            putchar(m->M[r][c].type);
        }
        putchar('\n');
    }
}

typedef enum dir {
    UP, RIGHT, DOWN, LEFT, FORWARD
} DIR;

typedef struct pos {
    int r, c;
    DIR dir;
} Pos;

typedef struct node {
    Pos pos;
    struct node *next;
} Node;

typedef struct queque {
    Node *head, *tail;
} Queque;

Queque *new_queque(void){
    Queque *q = malloc(sizeof(*q));
    q->head = q->tail = NULL;
    return q;
}

void enque(Queque *q, Pos pos){
    Node *node = malloc(sizeof(*node));
    node->pos = pos;
    node->next = NULL;
    if(q->head == NULL){
        q->head = q->tail = node;
    } else {
        q->tail = q->tail->next = node;
    }
}

Pos deque(Queque *q){
    Pos pos = q->head->pos;
    Node *temp = q->head;
    if((q->head = q->head->next)==NULL)
        q->tail = NULL;
    free(temp);
    return pos;
}

bool isEmpty_que(Queque *q){
    return q->head == NULL;
}

Pos dxdy(DIR curr, DIR next){
    Pos d = { 0, 0, 0};
    switch(curr){
    case UP:
        switch(next){
        case LEFT:
            d.c -= 1;
            break;
        case FORWARD:
            d.r -= 1;
            break;
        case RIGHT:
            d.c += 1;
            break;
        }
        break;
    case RIGHT:
        switch(next){
        case LEFT:
            d.r -= 1;
            break;
        case FORWARD:
            d.c += 1;
            break;
        case RIGHT:
            d.r += 1;
            break;
        }
        break;
    case DOWN:
        switch(next){
        case LEFT:
            d.c += 1;
            break;
        case FORWARD:
            d.r += 1;
            break;
        case RIGHT:
            d.c -= 1;
            break;
        }
        break;
    case LEFT:
        switch(next){
        case LEFT:
            d.r += 1;
            break;
        case FORWARD:
            d.c -= 1;
            break;
        case RIGHT:
            d.r -= 1;
            break;
        }
        break;
    }
    return d;
}

Pos next_pos(Pos pos, DIR dir){
    Pos dxy = dxdy(pos.dir, dir);
    switch(dir){
    case RIGHT:
        pos.dir = (pos.dir + 1) % 4;
        break;
    case LEFT:
        if((pos.dir = (pos.dir - 1)) < 0)
            pos.dir += 4;
        break;
    case FORWARD:
        break;
    }
    pos.r += dxy.r;
    pos.c += dxy.c;
    return pos;
}
static inline bool isValid(m_t *m, Pos pos){
    if(pos.r < 0 || pos.r >= m->height || pos.c < 0 || pos.c >= m->width || m->M[pos.r][pos.c].type == wall)
        return false;
    return true;
}
static inline bool isValidAndUnvisit(m_t *m, Pos pos){
    return isValid(m, pos) && !m->M[pos.r][pos.c].reachable;
}

void print_reachable(m_t *m){
    int i;
    for(i = 0; i < m->width; ++i)
        if(m->M[0][i].type == path_cell)
            break;
    Pos pos = { 0, i, DOWN};
    Queque *q = new_queque();
    enque(q, pos);
    while(!isEmpty_que(q)){
        pos = deque(q);
        if(!m->M[pos.r][pos.c].reachable){
            m->M[pos.r][pos.c].reachable = 1;

            Pos next = next_pos(pos, LEFT);
            if(isValidAndUnvisit(m, next))
                enque(q, next);
             next = next_pos(pos, FORWARD);
            if(isValidAndUnvisit(m, next))
                enque(q, next);
             next = next_pos(pos, RIGHT);
            if(isValidAndUnvisit(m, next))
                enque(q, next);
        }
    }
    free(q);
    for(int r = 0; r < m->height; ++r){
        for(int c = 0; c < m->width; ++c){
            if(m->M[r][c].reachable)
                putchar('+');
            else if(m->M[r][c].type == path_cell)
                putchar('-');
            else
                putchar(m->M[r][c].type);
        }
        putchar('\n');
    }
}

洪水填充算法迷宫

Flood fill algorithm maze

c

arrays

struct

maze