DFS 算法迷宫求解器

Question

我正在尝试使用 DFS 解决迷宫 algorithm.I 从文本文件中读取迷宫。方向顺序：西-北-东南-东。是否只有这样才能达到正确的解决方案？该程序不起作用。有没有我应该额外使用的构建？我卡在 DFS 分区上了。

#include <stdio.h>

char matrix[12][12];

void File()
{
        int i,j;
  

    FILE *file1;
    file1=fopen("maze.txt","r");
 
    for(i=0; i<12; i++){
        for(j=0;j<12;j++)
        {
        fscanf (file1, " %c", &matrix[i][j]);
        
        printf("%c ",matrix[i][j]);
       }
    printf("\n");
    }
}
void Print()
{
    int i,j;
    for(i=0;i<12;i++)
    {
        for(j=0;j<12;j++)
        {
            printf("%c ",matrix[i][j]);
            }
    printf("\n");       
    }
}
void stepDFS()
{
    int i,j;
    for(i=0;i<12;i++)
    {
        for(j=0;j<12;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;
}

maze.txt

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

当前输出：

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

Answer 1

函数体包裹着

if ( matrix[i][j]== '-' ) {
   ...
}

但是，matrix[i][j] == 's'第一次来电。所以你最终什么都不做！ s 应与 ..

等同对待

问题 #2：DFS 没有 return 值。

您声明 DFS return 是一个值（无论是否找到出口），然后检查其 return 值。但是您实际上 return 不是一个值。这没有任何意义，而且是未定义的行为。

你的编译器应该已经警告过你了。始终启用你的编译器警告——我使用 -Wall -Wextra -pedantic 和 gcc——并注意它们。

如果找到出口，您应该 returning 1（因为 matrix[i][j] == 'g' 或因为递归调用 returned 一个真值），或者 0 如果没有找到出口。

问题 #3：无限循环

没有什么可以阻止代码运行 E-W-E-W-E-W-E-W-E-...您很快会发现搜索进入了一个无限循环，当它用完堆栈时崩溃 space。

要解决此问题，请将方块更改为. 在递归调用之前，而不是之后。如果未找到出口，则在 returning.

之前将方块恢复为原始值（- 或 s）

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

一旦找到出口，

DFSreturns 为真值。（嗯，应该的，如上所述。）但是发生这种情况后你继续搜索！

一旦递归调用 return 是一个真值，它应该很简单 return。具体来说，它应该 return 本身是一个真值，传播在调用堆栈中找到出口的信息。

DFS 算法迷宫求解器

DFS Algorithm Maze Solver

c

algorithm

maze

depth-first-search