Maze solver using stacks and Queues

[maqalmulla]

Hello,
I have a Data structures project due and it's about developing a Maze solver that will solve the input from a maze using 2 methods, the depth first search and the breadth first search. we have been given only the code to input the maze in character arrays. We were also asked to use 2 classes a Cell class and Maze class. A maze class can be an example of a 2D array class object. I'm really confused and I don't know how to continue. Your help will be much appreciated.

Bellow is the code that I have so far.

 
#include <iostream>
#include <fstream>
#include <stack>
#include <queue>
#include <vector>

using namespace std;


class Cell{
public:
    Cell(){}
    Cell(bool a,bool b,bool c,bool d);
    Cell(Cell &copy);
    bool getTop(){ return top; }
    bool getBottom(){ return bottom; }
    bool getRight(){return right;}
    bool getLeft(){return left;}
    bool getVisited(){return visited;}
    bool getPrevCell(){return prevCell;}
    char getData(){return data;}
    void setTop(bool a ){top = a;}
    void setBottom(bool b){bottom = b;}
    void setRight(bool c){right = c;}
    void setLeft(bool d){left = d;}
    void setVisited(bool e){ visited = e; }
    void setPrevCell(bool f){prevCell = f;}
    void setData();
private:
    bool top, bottom, right, left, visited, prevCell;
    char data;
};

Cell::Cell(bool a,bool b,bool c,bool d){
    top = a;
    bottom = b;
    right = c;
    left = d;
}

Cell::Cell(Cell &copy){
    top = copy.top;
    bottom = copy.bottom;
    right = copy.right;
    left = copy.left;
}

class Maze{
    Maze(){}
    Maze(Cell m, Cell n);
private:
    vector<Cell> *maze;
};

Maze::Maze(Cell m, Cell n){
    *maze(m, n);
}

int main()
{
    ifstream in("maze.txt");
    char str1[100],str2[100],str3[100];
    in.getline(str1, 100);
    in.getline(str2, 100);
    in.getline(str3, 100);
    int line = 1, cell = 1; //variables are used for students to understand the reading structure
    while (!in.eof())
    {
        cell = 1;
        cout << "line " << line << endl;
        
        int i = 0;
        bool top, down, right, left; // to trace walls
        top = down = right = left = false;
        int j = 0, k = 1; // j for str2, k for str3
        Cell *c;
        while (i < strlen(str1)-1)
        {
            top = down = right = left = false;
            if (str1[i] == '+') i++; // new cell begins
            else if (str1[i] == '-') top = true; // wall above
            else if (str1[i] == ' ') top = false;
            //else error ...
            i = i + 3;
            if (str2[j] == '|') left = true; // left wall
            else if (str2[j] == ' ') left = false;
            //else error ...
            j = j + 4;
            if (str2[j] == '|') right = true; // right wall
            else if (str2[j] == ' ') right = false;
            //else error ...
            if (str3[k] == '-') down = true; // wall below
            else if (str3[k] == ' ') down = false;
            //else error ...
            k = k + 4;
            cout << "cell = " << cell++ << endl;
            cout << "Top :  " << top << "\t";
            cout << "down :  " << down << endl;
            cout << "right :  " << right << "\t";
            cout << "left :  " << left << endl;
            cout << endl << endl;
            c= new Cell(top, down, right, left);
            
            
        }
        strcpy(str1, str3);
        cout << str1 << endl;
        in.getline(str2, 100);
        in.getline(str3, 100);
        line++;
    }
    return 0;
}

Thank you very much

Sample Maze is something like:

+---+---+---+---+---+
    |               |
+   +   +   +---+---+
|   |   |           |
+   +---+---+---+   +
|   |               |
+   +   +---+---+   +
|       |           |
+---+---+   +---+---+
|                  
+---+---+---+---+---+

[tpb]

Post an example of an input maze. Put it in [output][/output] tags to preserve any spacing.

[nuderobmonkey]

Don't you rather need a two-dimensional array? That would be like:

vector<vector<char>> maze;

Then you need to write the maze.txt into the two-dimensional maze array. I don't know how maze.txt is formatted, thus I assume that each line represents a row. Then your read-in would be:

void read_mazefile( istream & is, vector<vector<char>> & maze_v)
{
    string line;
    maze_v.clear();
    while( getline(is, line) )
    {
        vector<char> row_v;
        for( int i = 0; i < line.length(); ++i)
        {
            row_v.push_back(line[i]);
        }
        maze_v.push_back(row_v);
    }
}

Then you can use the the two-dimensional vector like a two-dimensional array:

for( int i = 0; i < maze.size(); ++i)
{
    for (int k = 0; k < maze[i].size(); ++k)
    {
        cout << maze[i][k];
    }
    cout << '\n';
}

I hope that these hints will help you a bit at designing your program. Maybe, you need to encapsulate the matrix inside a class and change the 'char' type to 'Cell' objects.
*edited

[maqalmulla]

@nuderobmonkey the thing is, I need the maze object to be a 2D array of Cells. I have edited my code after asking my instructor for help and this is what I've come with till now. I'm currently not sure how to push the elements and since they are 2D vector objects as class members.

[maqalmulla]

@tqb Done!

[nuderobmonkey]

Hello maqaimulla, I don't know what you want to do with the code you have posted above, maybe I'm totaly on stick or at your approach is something wrong.

Below I've posted some code which shows how I self would starting the exercise. I think it provides all the stuff you need. The last thing (and perhaps the most challenging) is to implement the breadt- and the dept seach with stacked and queued cells.

#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std;

// A cell obect holds its ordinates and its cell content.
//
class Cell
{
public:    
    Cell( int row, int col, char hold)
    : m_row(row), m_col(col), m_hold(hold), m_visited(false)
    {}
    char hold() const { return m_hold; }
    int row() const { return m_row; }
    int col() const { return m_col; }
    bool visited() const { return m_visited; }
    void setVisited( bool visited = true) { m_visited = visited; }
private:
    char m_hold; // content of cell
    int m_row; 
    int m_col;
    bool m_visited;
};

// A maze objects holds all cells and provides its cell content.
//
class Maze
{
public:
    Cell & cell( int row, int col) { return m_maze[row][col]; }
    void clear() { m_maze.clear(); }
    void setMazeVector( vector<vector<Cell>> maze ) 
    { m_maze = maze; m_rowSize = maze.size(); m_colSize = maze[0].size(); }
    const size_t rowSize() const { return m_rowSize; }
    const size_t colSize() const { return m_colSize; }
    
    // Needs'friend' declaration because then it will have
    // access to the m_maze vector.
    friend ostream & operator<<(ostream & os, const Maze & maze);
    
private:
    vector<vector<Cell>> m_maze;  
    size_t m_rowSize;
    size_t m_colSize;      
};

// This overloads the << operator,
// for being able streaming Maze obects to any ostream.
//
ostream & operator<<( ostream & os, const Maze & maze)
{
    for( auto & row : maze.m_maze)
    {
        for( auto & cell : row)
        {
            os << cell.hold();
        }
        os << '\n';
    }
    return os;
}

void read_maze( istream & is, Maze & maze)
{
    maze.clear();
    string input;
    vector<vector<Cell>> maze_v;
    int row, col;
    row = 0;
    while( getline(is,input) )
    {
        vector<Cell> row_v;
        for( col = 0; col < input.length(); ++col)
        {
            Cell cell( row, col, input[col]);
            row_v.push_back(cell);
        }
        maze_v.push_back(row_v);
        ++row;
    }
    maze.setMazeVector(maze_v);
}

int main()
{
     ifstream ifs("maze.txt");
     
     Maze maze;
     read_maze(ifs, maze);
     cout << maze;
}

And feel free to ask is something is unclear to you.

[maqalmulla]

@nuderobmonkey Thank you so much for your great help!