DFS Algorithm Maze Solver-CodePudding

I am trying to solve the maze using DFS algorithm.I read the maze from the text file. direction order :west-north-south-east. Is it possible to reach the right solution only in this way? The program does not work. Is there a build I should use additionally ?I'm stuck on DFS partition.

#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 #            
# # # # # # # # # # # #

current output:

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

CodePudding user response：

The function body is wrapped with

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

But, matrix[i][j] == 's' for the first call. So you end up doing nothing at all! s should be treated equivalently to ..

Problem #2: DFS doesn't return a value.

You declare that DFS returns a value (whether the exit was found or not), and you check its return value. But you don't actually return a value. This makes no sense, and it's undefined behaviour.

Your compiler should have warned you about this. Always enable your compilers warnings — I use -Wall -Wextra -pedantic with gcc — and heed them.

You should be returning 1 if the exit was found (either because matrix[i][j] == 'g' or because a recursive call returned a true value), or 0 if the exit wasn't found.

Problem #3: Infinite loops

Nothing stops the code from going E-W-E-W-E-W-E-W-E-... You will quickly find the search enter an infinite loop, crashing when it runs out of stack space.

To solve this, change the square to . before the recursive call, not after. If the exit isn't found, restore the square to its original value (- or s) before returning.

Problem #4: You keep searching after finding a solution.

DFS returns a true value once the exit was found. (Well, it should, as mentioned above.) But you continue searching after this happens!

Once a recursive call returns a true value, it should simple return. Specifically, it should return a true value itself, propagating the information that the exit was found up the call stack.