DFS 알고리즘 미로 생성자

Question

DFS 알고리즘을 사용하여 ASCII로 미로를 생성하려고합니다 ('#'은 벽을 나타내고 ''여유 공간 ')는 왼쪽 위 모서리를 시작으로하고 오른쪽 하단을 종료합니다 모서리. 문제는 미로가 창조를 시작한 후 모든 이웃이 이미 방문했기 때문에 차단 된 것입니다.

왼쪽 위 모퉁이에서 시작하여 셀을 방문한 것으로 표시하고 ''(여유 공간을 나타냄)를 입력 한 다음 셀의 이웃을 임의로 선택하고 동일한 작업을 수행합니다. 그러나 나는 이것을 while 루프에 넣었고 이것이 좋은 생각이 아니라고 확신합니다. 는 DFS의 여기

내 시도 : 구조 중에

int  generation(t_maze *maze, int pos_y, int pos_x)                                        
{                                                     
    int dest;                                                  

    maze->maze[pos_y][pos_x] = ' ';                                             
    maze->visited[pos_y][pos_x] = '1';                                             
    while (maze->maze[maze->height - 1][maze->width - 1] == '#')                                      
    {                                                    
     if ((dest = my_rand(1, 4)) == 1 && pos_y - 1 >= 0 && maze->visited[pos_y - 1][pos_x] == '0')                             
     generation(maze, pos_y - 1, pos_x);                                           
     else if (dest == 2 && pos_x + 1 < maze->width && maze->visited[pos_y][pos_x + 1] == '0')                              
     generation(maze, pos_y, pos_x + 1);                                           
     else if (dest == 3 && pos_y + 1 < maze->height && maze->visited[pos_y + 1][pos_x] == '0')                              
     generation(maze, pos_y + 1, pos_x);                                           
     else if (dest == 4 && pos_x - 1 >= 0 && maze->visited[pos_y][pos_x - 1] == '0')                                
     generation(maze, pos_y, pos_x - 1);                                           
     my_showtab(maze->maze); //it prints the 2d array                                              
     usleep(50000);                                                 
    } 


typedef struct s_maze                                                
{                                                     
    int   width;                                                
    int   height;                                                
    char   **maze;                                                
    char   **visited;                                               
}    t_maze; 

는 폭이 예상되는 2 차원 배열이 작성 될 미로 미로의 높이 미로 높이의 폭이고 방문하지 않은, 1 : 방문 #의 ' '로 '와'0, 1, 0과 2 차원 배열입니다

내가이 (작은 예) 같은 미로

,758,483을 갖고 싶어 방문210

Answer 1

코드는 하나의 다음 셀로 항상 이동하기 때문에 하나의 경로를 만듭니다. 그것은 dfs가 아닙니다. 당신은 그런 식으로 그것을 할 수 :

def dfs(x, y): 
    visited[x][y] = true 
    maze[x][y] = ' ' 
    next_cell = random unvisited neighbors of (x, y): 
    dfs(next_cell.x, next_cell.y) 

요점은 : 당신은 어떤 시점에서 역 추적 할 필요가 (그것을 위해 재귀를 사용하는 것이 편리합니다). 단일 경로가 원하는 모양으로 보이지 않습니다 (멈추거나 출구에 도달하지 못할 수도 있음).