0

Working on the maze program, with '*' indicating a wall, ' ' indicating a corridor, and '#' indicating a solution path, where I must use a recursive backtracking algorithm, I cannot seem to print the '#' symbol for the solved maze. Here is my new code:

#include<iostream>
#include<fstream>
using namespace std;

#define MAXROW 24 // Maximum number of rows
#define MAXCOL 81 // Maximum number of columns

// Return false if the current square location [m][n] is outside the maze
// or it is a wall('*') or an already marked('x'). Otherwise, the square
// is a valid move and the function returns true.
int validate(char a[MAXROW][MAXCOL], int rows, int columns, int m, int n)
{
    int flag = 1;
    if(m < 0 || m >= rows || m < 0 || m >= columns)
    {
        flag = 0;
    }
    if(flag && (a[m][n] == '*' || a[m][n] == 'x'))
    {
        flag = 0;
    }
    return flag;
}

// Read a maze from a file.
void readMaze(ifstream &in, int &rows, int &columns, char a[MAXROW][MAXCOL])
{    
    in >> rows >> columns;
    cout << rows << " " << columns << endl;
    in.getline(a[0],sizeof a[0]);
    for(int i = 0; i < rows; i++)
    {
        in.getline(a[i], sizeof a[i]);
    }
}

// Print the maze.
void printMaze(int &rows, int &columns, char a[MAXCOL][MAXCOL])
{   
    for(int i = 0; i < rows; i++)
    {
        for(int j = 0; j < columns; j++)
        {
            cout << a[i][j];
        }
        cout << endl;
    }
}

// Create a solution to the maze from point [sm,sn] (s = start and e = end).
// Return true if the maze has a solution, otherwise false. This function
// uses recursion backtracking to solve mazes that result from marking the
// current square and moving up one step along each open square. Paths are
// tried in the directions in this order: up, right, down, left. The '#'
// represents a solution path.
int solveMaze(int rows, int columns, char a[MAXROW][MAXCOL], int sm, int sn,
               int em, int en)
{
    int finished;

    // Return false if there is no solution.
    if(!validate(a,rows,columns,sm,sn))
    {
        return 0;
    }
    // Return true and mark solution path.
    else if(sm == em && sn == en)
    {
        a[sm][sn] = '#';
        return 1;
    }
    else
    {
        a[sm][sn] = 'x'; // Mark repeated paths.
        printMaze(rows,columns,a);
        finished = solveMaze(rows,columns,a,sm-1,sn,em,en); // Move left.
        if(!finished) // Move down.
        {
            finished = solveMaze(rows,columns,a,sm,sn+1,em,en);
        }
        if(!finished) // Move right.
        {
            finished = solveMaze(rows,columns,a,sm+1,sn,em,en);
        }
        if(!finished) // Move up.
        {
            finished = solveMaze(rows,columns,a,sm,sn-1,em,en);
        }
        if(finished) // Mark solution path.
        {
            a[sm][sn] = '#';
        }
        return finished;
    }
}

int main()
{
    char inFile[20];
    char a[MAXROW][MAXCOL];
    ifstream in;
    int rows, columns, sm, sn, em, en;

    // Prompt user for file name.
    cout << "Enter file name: ";
    cin >> inFile;

    // Check for file open errors.
    if(!inFile)
    {
        cout << "Error" << endl;
        return -1;
    }

    // Open the file.
    in.open(inFile);

    cout << "Maze before solution: " << endl;
    readMaze(in,rows,columns,a);
    printMaze(rows,columns,a);
    cout << "Maze after solution: " << endl;
    solveMaze(rows,columns,a,sm,sn,em,en);
    printMaze(rows,columns,a);

    // Close the file.
    in.close();
    return 0;
}

Here is my output:

Enter file name: maze.txt
Maze before solution:
8 12
  **********
* *        *
*   ****** *
*****      *
*     ******
*** ***    *
*       ** *
**********
Maze after solution:
  **********
* *        *
*   ****** *
*****      *
*     ******
*** ***    *
*       ** *
**********

Here is the expected output:

Enter file name: maze.txt
Maze before solution:
8 12
  **********
* *        *
*   ****** *
*****      *
*     ******
*** ***    *
*       ** *
**********
Maze after solution:

##**********
*#*########*
*###******#*
*****######*
*  ###******
***#***####*
*  #####**#*
**********##

The only part I am having trouble with is printing the '#' symbol. What do I need to add/change in order to print this?

2
Contributors
1
Reply
31
Views
4 Years
Discussion Span
Last Post by kal_crazy
0

The program doesn't know what the end of the maze is. You did not specify what is the end. I would assume em and en are end m and end n but they are initialized to nothing.

The end is MAXROW-1 and MAXCOL-1, right? So define em and en to MAXROW-1 and MAXCOL-1.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.