洪水填补算法迷宫

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

试试这个

#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'); 
    } 
} 

Answer 2

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

如果是路径，则将其更改为可访问并访问，然后在每个方向调用flood_fill。

如果是墙壁或访问路径，则不需要进一步调用即可返回到flood_fill。

flood_fill已返回后，任何未访问路径的位置都无法访问。

编辑：

为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 3

首先，你可以找到迷宫递归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)。