洪水填補算法迷宮

-2

我是個努力使我的程序讀取這樣的迷宮：洪水填補算法迷宮

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

並打印出迷宮可達區和非可到達的區域，這應該是這樣的：

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

牆用「＃」表示，可通過的單元格用「。」表示。

取代單元格的「+」意味着那些單元格可從迷宮的頂部入口點到達。「 - 」符號是進入迷宮頂部時無法到達的細胞。

例如，在上述迷宮中，除了右下角的單元格之外，所有單元格都是可到達的。這是因爲這些細胞無法從迷宮頂部的入口點到達。

我想用一些遞歸來填充迷宮，並確定可達區域，但我遇到了麻煩。

這是我到目前爲止有：

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功能沒有做正確的事，而且我有困難得到它的權利。任何人都可以幫助我，請讓我的代碼正確填充代碼的一部分，以便我可以在代碼中的其他地方調用函數，並確定可以到達哪些單元格。

來源

2016-05-13 RoadRunner

試試這個

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

來源

2016-05-15 20:34:19 BLUEPIXY

[DEMO]（http://ideone.com/SABKsZ） – BLUEPIXY

非常感謝你回答這個問題BLUEPIXY :) – RoadRunner

我意識到你爲此付出了很多努力，而且我非常感謝。我標記你的答案是正確的。你知道我可以如何實現這個問題http://stackoverflow.com/questions/37303378/finding-a-cost-for-a-maze-path。 @BLUEPIXY – RoadRunner

您需要檢查當前位置是路徑，訪問路徑還是牆。

如果是路徑，則將其更改爲可訪問並訪問，然後在每個方向調用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 */ 
}

來源

2016-05-13 11:59:23

三江源非常多的答案。我設法得到了更近一點:) – RoadRunner

你能解釋一下你當前位置的含義嗎？我認爲那就是我要去錯的地方@KlasLindbäck。 – RoadRunner

當前位置應該是您檢查，向下，向左，向右單元格的迷宮單元。 – Mirakurun

首先，你可以找到迷宮遞歸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)。

來源

2016-05-15 17:34:05

是的，我試圖在我的示例函數中調用它，但我認爲我沒有做對。是我的榜樣功能正確，我正在尋找迷宮的入口。 – RoadRunner

第一行只有一個'.'嗎？如果是，那麼你在做什麼是好的。順便說一下，我編輯我的文章使用'.type'，檢查這不是你的問題。 –

是的，我有我的函數「determine_reachable_cells（m_t * maze）」，類型爲int。我相信我應該改變它以輸入void。 – RoadRunner

洪水填補算法迷宮

回答

相關問題