My recursive maze solver does not recognize start position correctly

Question

I'm trying to write the code for a recursive maze solver. This is what I have so far:

const int NROWS = 5;
const int MCOLS = 12;

// Symbols:
// ' ' = open
// 'X' = blocked
// 'S' = start
// 'E' = goal
// '.' = path
// '+' = bad path

char maze[NROWS][MCOLS+1] = {
    {"S XXXXXXXXXX"},
    {"X  X   XX  X"},
    {"XX   XX X XX"},
    {"XX X       X"},
    {"XXXXXXXXXEXX"},
    };


void display_maze(void);
bool find_path(int x, int y);


int main()
{
    display_maze();

    if ( find_path(0, 0) == true )
        printf("Success!\n");
    else
        printf("Failed\n");

    display_maze();

    return 0;
}



void display_maze()
{
    int i;

    printf("MAZE:\n");
    for ( i = 0; i < NROWS; i++ )
    printf("%.*s\n", MCOLS, maze[i]);
    printf("\n");

    return;
}


bool find_path(int x, int y)
{
    // If x,y is outside maze, return false.
    if ( x < 0 || x > MCOLS - 1 || y < 0 || y > NROWS - 1 ) return false;

    // If x,y is the goal, return true.
    if ( maze[y][x] == 'E' ) return true;

    // If x,y is not open, return false.
    if ( maze[y][x] != ' ' && maze[y][x] != 'S' ) return false;

    // Mark x,y part of solution path.
    maze[y][x] = '.';

    // If find_path North of x,y is true, return true.
    if ( find_path(x, y - 1) == true ) return true;

    // If find_path East of x,y is true, return true.
    if ( find_path(x + 1, y) == true ) return true;

    // If find_path South of x,y is true, return true.
    if ( find_path(x, y + 1) == true ) return true;

    // If find_path West of x,y is true, return true.
    if ( find_path(x - 1, y) == true ) return true;

    // Unmark x,y as part of solution path.
    maze[y][x] = '+';

    return false;
}

For this iteration of the maze, it works fine. The output prints "Success" and shows the pathway from 'S' to 'E'.

However, should I move the position of 'S' like so:

XXXXXXSXXXXX
X  X   XX  X
XXX  XX X XX
XX X       X
XXXXX XXXEXX

The output prints "Failed". I have a feeling that from the recursion code I've written, my maze automatically fails if it does not find ' ' or 'S' right away. I'm just not sure how to implement the code to keep searching for the 'S' though.

Another question- As you can see, I implemented a sample maze within my .cpp file. However, my end goal is to stream a maze from a .txt file. Each maze will thus have different dimensions. Would it make more sense for me to use a vector then rather than a char array?

Answer 1

For the maze,

XXXXXXSXXXXX
X  X   XX  X
XXX  XX X XX
XX X       X
XXXXX XXXEXX

when you are calling find_path() with parameter (0,0) which contains X in that position. So

 if ( maze[y][x] != ' ' && maze[y][x] != 'S' ) return false;

is executed in find_path() which returns false. So output is Failed.

You must find out the position of 'S' and then call find_path() with those parameters.

For your second question:

You can use vector or STL string too. You can use character type array too, if you know the max number of row given in the .txt file.