带 DFS 的迷宫求解器

Question

我正在尝试使用 DFS 解决迷宫问题 algorithm.ORDER：西-北-南-东我的输出符合这个逻辑 Labyrinth picture1。点(3,3)之后不应该往上走，因为优先顺序是西。我该怎么办？

#include <stdio.h>

char matrix[8][8];

void File()
{
        int i,j;
  

    FILE *file1;
    file1=fopen("maze1.txt","r");
 
    for(i=0; i<8; i++){
        for(j=0;j<8;j++)
        {
        fscanf (file1, " %c", &matrix[i][j]);
        
        printf("%c ",matrix[i][j]);
       }
    printf("\n");
    }
}
void Print()
{
    int i,j;
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            printf("%c ",matrix[i][j]);
            }
    printf("\n");       
    }
}
void stepDFS()
{
    int i,j;
    for(i=0;i<8;i++)
    {
        for(j=0;j<8;j++)
        {
            if(matrix[i][j] == 's')
            {
                
                    DFS(i,j);
                        
               
            
            }
            
        }
    printf("\n");       
    }
    
}
 DFS(int i,int j)
{
    if(matrix[i][j-1] == '-')
    {
        matrix[i][j-1] = '.';
        DFS(i,j-1);
    }
     if(matrix[i-1][j] == '-')
    {
        matrix[i-1][j] = '.';
        DFS(i-1,j);
    }
     if(matrix[i+1][j] == '-')
    {
        matrix[i+1][j] = '.';
        DFS(i+1,j);

    }
     if(matrix[i][j+1] == '-')
    {
        matrix[i][j+1] = '.';
       DFS(i,j+1);

    }
    
    
}
int main()
{
    File();
    Print();
    stepDFS();
    Print();
    return 0;
}

maze1.txt (#wall - null.step)

# # # # # # # #  
# g - - # - - #       
# # # - - - # # 
# - # # - - - # 
# - - # - - - #
# - - - - # # # 
# - - # - - s #
# # # # # # # #

输出

# # # # # # # #
# g . . # . . #
# # # . . . # #
# . # # . . . #
# . . # . . . #
# . . . . # # #
# . . # . . s #
# # # # # # # #

我不知道这是否应该是输出

# # # # # # # #  
# g . . # - - #       
# # # . . - # # 
# . # # . - - # 
# . . # . - - #
# . . . . # # # 
# - - # . . s #
# # # # # # # #

-------------更新------------- 一步一步

#include <stdio.h>

char matrix[8][8];

void ReadFile()
{
    printf("\n\n\n                START MAZE    ");
    int x,y;
    FILE *file1;
    file1=fopen("myMaze.txt","r");
 
    for(x=0; x<8; x++){
        for(y=0;y<8;y++)
        {
        fscanf (file1, " %c", &matrix[x][y]);
        
      
       }
    printf("\n");
    }
}



void PrintMaze()
{ 
    int x,y;
    for(x=0;x<8;x++)
    {
        printf("                ");
        for(y=0;y<8;y++)
        {
             
            printf(" %c ",matrix[x][y]);
        }
     
    printf("\n");       
    }
    printf("\n\n\n\n");
}
  
  
int DFS(int x,int y){
 

 
    if(matrix[x][y]=='g') // goal
    {
        return 1;
    }
      if(matrix[x][y-1] == '-' ){ //WEST
           

        
        matrix[x][y-1] = '.';
        PrintMaze();
        
        
        if(DFS(x,y-1)){
            
            matrix[x][y-1] ='.'; 
            PrintMaze();
            
            return 1;
        }
        else{
            DFS(x,y-1);
            return 0;
        
         }
         DFS(x,y-1);
      

     }
      if(matrix[x-1][y] == '-'){  //NORTH
       
   
        matrix[x-1][y] = '.';
        PrintMaze();
        
        if(DFS(x-1,y)){
            
            matrix[x-1][y] = '.';
            PrintMaze();
            
            return 1;
        }
        else{
            DFS(x-1,y);
            return 0;
        }
     
         DFS(x-1,y);
    

     }
    
    
 
    
    
    
       if(matrix[x+1][y] == '-'){ //SOUTH
             
     
        matrix[x+1][y] = '.';
        PrintMaze();
        
        if(DFS(x+1,y)){
            
           matrix[x+1][y] ='.'; 
           PrintMaze();
            
            return 1;
            
        }
        else{
          DFS(x+1,y);
            return 0;
        }
        
        DFS(x+1,y);
 
    }  
  
    
           if(matrix[x][y+1] == '-'){     //EAST
          

        matrix[x][y+1] = '.';
       
        if(DFS(x,y+1)){
            
        matrix[x][y+1] = '.'; 
        PrintMaze();
          
            return 1;
        }
        else{
            DFS(x,y+1);
            return 0;
        }
        
        DFS(x,y+1);
    
    }
    
 

    return 0;


}


void StartSearch()
{ 
    printf("                  STEP BY STEP");

    int x,y;

 
    for(x=0;x<8;x++)
    {
        for(y=0;y<8;y++)
        {
            if(matrix[x][y] == 's')//start
            {
              DFS(x,y);
 
             }
        }
        
    printf("\n");  
         
    }
 
}
 
int main()
{
    ReadFile();
    
    PrintMaze();
    
    StartSearch();
    
    PrintMaze();
    
    return 0;
}

myMaze.txt

# # # # # # # #  
# g - - # - - #       
# # # - - - # # 
# - # # - - - # 
# - - # - - - #
# - - - - # # # 
# - - # - - s #
# # # # # # # #

DFS 确定方向时首先考虑 function.Other 方向内的条件。

Answer 1

首先，启用并注意编译器的警告！（对于 gcc，我使用 -Wall -Wextra -pedantic）。你已经被告知了这一点。当编译器可以为您解答您的问题时，为什么还要来 SO！

DFS(int i,int j) 表示 int DFS(int i,int j)，但您打算使用 void DFS(int i,int j)。（不过，这不是您所需要的。您已经拥有了您所需要的。）

接下来，让我们确定预期的输出，因为您不确定。这个迷宫有五个解决方案（忽略无意义地访问一个单元格两次的解决方案）。

Length = 9
# # # # # # # #
# g . . # - - #
# # # . . - # #
# - # # . - - #
# - - # . - - #
# - - - . # # #
# - - # . . s #
# # # # # # # #

Length = 11
# # # # # # # #        # # # # # # # #
# g . . # - - #        # g . . # - - #
# # # . . - # #        # # # . . . # #
# - # # . . - #        # - # # - . - #
# - - # . . - #        # - - # . . - #
# - - - . # # #        # - - - . # # #
# - - # . . s #        # - - # . . s #
# # # # # # # #        # # # # # # # #

Length = 13
# # # # # # # #        # # # # # # # #
# g . . # - - #        # g . . # - - #
# # # . . - # #        # # # . . . # #
# - # # . . . #        # - # # - . . #
# - - # . . . #        # - - # . . . #
# - - - . # # #        # - - - . # # #
# - - # . . s #        # - - # . . s #
# # # # # # # #        # # # # # # # #

其中任何一个都是有效的输出。显然，第一条路径比其他两条路径短，但 DFS 不会（必然）找到最短路径。（你需要一个 BFS。）

关于问题。

你有两个问题：

您正在标记您访问过的每个单元格，无论它是否是路径的一部分。
您永远不会停止搜索，因此您最终会访问每个可到达的单元格。

为了解决这两个问题，需要做一个重要的改变。 DFS 需要 return 由其参数标识的单元格是否是路径的一部分。

如果单元格是路径的一部分，

DFS 应该 return 1，如果不是，则 0。

那么你怎么知道单元格是否是路径的一部分？

如果当前单元格是 g，则当前单元格是路径的一部分。
如果北方的单元格是路径的一部分（即如果 DFS(y-1,x) return 为真值），则当前单元格是路径的一部分。
如果南边的单元格是路径的一部分（即，如果 DFS(y+1,x) return 为真值），则当前单元格是路径的一部分。
如果西边的单元格是路径的一部分（即如果 DFS(y,x-1) return 为真值），则当前单元格是路径的一部分。
如果东边的单元格是路径的一部分（即如果 DFS(y,x+1) return 为真值），则当前单元格是路径的一部分。
否则，单元格不是路径的一部分。

问题 #2：找到解决方案后您继续搜索。

只要您知道单元格是路径的一部分，DFS 就应该 return。立即地。如果北边的单元格是路径的一部分，请不要继续检查南边的节点！

问题 #1：您正在标记您访问过的每个单元格

当您输入 DFS 时，您通过将单元格设置为 . 将其标记为路径的一部分。这很好，因为它可以防止无限循环。

但它可能最终不会成为路径的一部分。，如果发现它不是路径的一部分，则需要将其值恢复为-。

带 DFS 的迷宫求解器

Maze solver with DFS

c

algorithm

maze

depth-first-search