Note: second post contains more info about where I'm having a problem... what I'm expecting to do and what the program is actually doing.

Hey all, I'm finishing up an assignment for my C++ class and I can't figure out why the program stops in the middle of it.

The assignment is a maze, the maze is a vector of vectors of binary numbers. 8 is north, 4 is east, 2 is south and 1 is west. The input file that I'm working on is formatted as such:

[total rows][total columns]
[startrow][startcolumn]
[finishrow][finishcolumn]
[cell[0][0]] [cell[0][1] .... [cell[0][totalcolumns-1]
..
...
[cell[totalrows-1][0]].... [cell[totalrows-1][totalcolumns-1]]

if that makes any sense at all... here is my input file:

5 4
4 3
1 0
 6 1 0 0 
10 0 6 3 
12 5 9 10 
 0 0 0 10 
 0 0 0 8

Now I am able to construct the maze and move through it until I try to go south, it just starts popping my stack until it gets to the end. Any suggestions? Heres my code thus far:

Maze.h

//Maze.h


#ifndef MAZE
#define MAZE

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

using namespace std;

struct MazeCell
{
        short int doorEncoding; // Range 0..15.
       // north = doorEncoding & 0x08
       // east = doorEncoding & 0x04
       // south = doorEncoding & 0x02
       // west = doorEncoding & 0x01
       // Note that the result of these operations is not
       // necessarily 1, but some non-zero value if there
       // is in that particular direction. 0 else.
       bool visited;
       int parentRow;
       int parentCol;
       char direction;
};

struct CellPosition
{
        int row;
        int col;
}; // useful as StackItem or QueueItem.

class Maze
{
      public:
      
      Maze();    
      Maze(const string& fileName); // Load from file.
      void Solve(); // Solve the maze.
      void PrintSolution();
      //CellPosition getMouse();
           
              
      vector <vector<MazeCell> > maze; // maze square
      int rows; // number of rows
      int cols; // number of columns
      int mouseRow; // row position of mouse
      int mouseCol; // col position of mouse
      int cheeseRow; // row position of cheese
      int cheeseCol; // col position of cheese
      int squaresVisited;
      bool solved;
}; //Maze

#endif

Maze.cpp

//maze.cpp

#include "maze.h"
#include <stack>

using namespace std;

Maze::Maze()
{
            rows = 0;
            cols = 0;
            mouseRow = 0;
            mouseCol = 0;
            cheeseRow = 0;
            cheeseCol = 0;
            squaresVisited = 0;
}

Maze::Maze(const string& fileName)
{
    rows = 0;
    cols = 0;
    mouseRow = 0;
    mouseCol = 0;
    cheeseRow = 0;
    cheeseCol = 0;
    squaresVisited = 0;
    int m, n;
    ifstream maze_in;
    
    // declare variable to open file etc.
   maze_in.open(fileName.c_str(), ios::in);
    
    // read m and n and init rows and cols.
    maze_in >> m >> n >> mouseRow >> mouseCol;
    maze_in >> cheeseRow >> cheeseCol;
    cout << "mouseRow in constructor is " << mouseRow << endl;
    rows = m;
    cols = n;
    // read and init mouse and cheese positions.
    // Now we know the size of maze. let us init.
    // Reserve space for rows (= n) many rows.
    maze.resize(m);
    // reserve space for cols (= n) many columns in each row.
    for (int rowNum = 0; rowNum < rows; rowNum++)
    {
        maze[rowNum].resize(cols);
    }
    
    for (int rowNum = 0; rowNum < rows; rowNum++)
    {
        for (int colNum = 0; colNum < cols; colNum++)
        {
        maze_in >> maze[rowNum][colNum].doorEncoding;
        maze[rowNum][colNum].visited = 0;
        maze[rowNum][colNum].parentRow = 0;
        maze[rowNum][colNum].parentCol = 0;
        maze[rowNum][colNum].direction = ' ';
        }
        
    }
    
    cout << "cell 1,2 doorEncoding is " << maze[1][2].doorEncoding << endl;
    
    // Now we can use maze[0][0] ... maze[n-1][m-1].
    // Read and initialize all the cells 
    cout << "done reading maze" << endl;
    maze_in.close();
}

/*Maze::CellPosition getMouse()
{
 CellPosition mouse;
 mouse.row = mouseRow;
 mouse.col = mouseCol;
 return mouse;
}*/

void Maze::Solve() // Solve the maze.
{
     
     stack<CellPosition> path;
     char dir;
     CellPosition current;
     bool unsolvable = false;
     int i = 0;
     
     cout << "mouseRow in solve is " << mouseRow << endl;
     
     current.row = mouseRow;
     current.col = mouseCol;  
     
     cout << "setting parent for mouse" << endl;
     
     maze[current.row][current.col].parentRow = -1;
     maze[current.row][current.col].parentCol = -1;
     maze[current.row][current.col].direction = ' ';
     maze[current.row][current.col].visited = true;
     
     cout << "adding that to the stack..." << endl;
     
     path.push(current);
     cout << endl;
     cout << endl;
     cout << i;
          
     while(!unsolvable || (current.row == cheeseRow && current.col == cheeseCol))
     {
         

          if (maze[current.row][current.col].doorEncoding& 0x08 && maze[current.row-1][current.col].visited != true)
          {
                          maze[current.row-1][current.col].parentRow = current.row;
                          maze[current.row-1][current.col].parentCol = current.col;
                          maze[current.row-1][current.col].visited = true;
                          cout << current.row << " " << current.col << endl;
                          path.push(current);
                          current.row = current.row - 1;
                          ++squaresVisited;
                          
                          
          }
          
          else if(maze[current.row][current.col].doorEncoding& 0x04 && maze[current.row][current.col+1].visited != true)
          {
                                                               
                          maze[current.row][current.col+1].parentRow = current.row;
                          maze[current.row][current.col+1].parentCol = current.col;
                          maze[current.row][current.col+1].visited = true;
                          cout << current.row << " " << current.col << endl;
                          path.push(current);
                          current.col = current.col + 1;
                          ++squaresVisited;
          }
          
          
          else if(maze[current.row][current.col].doorEncoding& 0x02 && maze[current.row+1][current.col].visited != true)
          {
                                                               cout << "goin south" << endl;
                          maze[current.row+1][current.col].parentRow = current.row;
                          maze[current.row+1][current.col].parentCol = current.col;
                          maze[current.row+1][current.col].visited = true;
                          cout << current.row << " " << current.col << endl;
                          path.push(current);
                          current.row = current.row + 1;
                          ++squaresVisited;
          }
          
          else if(maze[current.row][current.col].doorEncoding& 0x01 && maze[current.row][current.col-1].visited != true)
          {
                                                               cout << " blah " << endl;
                          maze[current.row][current.col-1].parentRow = current.row;
                          maze[current.row][current.col-1].parentCol = current.col;
                          maze[current.row][current.col-1].visited = true;
                          cout << current.row << " " << current.col << endl;
                          path.push(current);
                          current.row = current.col - 1;
                          cout << current.row << " " << current.col << endl;
                          ++squaresVisited;
          }
          
          else if (path.empty())
             unsolvable = false;
          
          else
          {
           path.pop();
           current.row = path.top().row;
           current.col = path.top().col;
           if(path.empty())
             unsolvable = true;
          }          
     }
     if (current.row == cheeseRow && current.col == cheeseCol)
     solved = true;
     else
     cout << "no dice" << endl;
    
}

void Maze::PrintSolution()
{
     stack<char> tempStack;
     CellPosition current;
     char direction;
     
     current.row = cheeseRow;
     current.col = cheeseCol;
     
     while(maze[current.col][current.row].parentRow != -1)
     {
         if(maze[current.col][current.row].parentRow > current.row)
            direction = 'N';
         else if(maze[current.col][current.row].parentRow < current.row)
              direction = 'S';
         else if(maze[current.col][current.row].parentCol > current.col)
              direction = 'W';
         else if(maze[current.col][current.row].parentCol < current.col)
              direction = 'E';
         current.col = maze[current.col][current.row].parentCol;
         current.row = maze[current.col][current.row].parentRow;
         tempStack.push(direction);
         
     }
     
     while(!tempStack.empty())
     {
      char tempChar = tempStack.top();
      cout << tempChar << " ";
     }
}

mazeDriver.cpp

//MazeDriver.cpp

#include "maze.h"

using namespace std;

int main()
{
    string fileName;
    
    cout << "Please enter the filename for the maze" << endl;
    cin >> fileName;
    
    Maze theMaze;
    
    theMaze = Maze(fileName);
    cout << "attempting to solve" << endl;
    theMaze.Solve();
    
    theMaze.PrintSolution();
    
    cout << "epic fail " << endl;
    
    char trash;
    cin >> trash;
    
    return 0;
}

Any help is very very appreciated... I'm stumped =( A point in the right direction would be mucho appreciated! I have a feeling it's a stupid error somewhere.

It seems like it should go south, but it never makes it past the if function and then just proceeds to pop everything from the stack!

Also, the code here basically takes the binary input, sees if it can go a direction that hasnt been visited yet. If it can it adds the last cell to the stack and the current cell is modified to the cell that it can go to and its visited value is changed to true. If it comes to a dead end it pops the stack until it comes to a place where it can go to a cell that has not been visited yet.

The problem I am having is with this specific function (sorry for posting all that code up there... but I suppose I'll leave it there for reference because I'm not sure exactly where the problem is originating from). Heres the if statement, from the Solve() function:

else if(maze[current.row][current.col].doorEncoding& 0x02 && maze[current.row+1][current.col].visited != true)
          {
                                                               cout << "goin south" << endl;
                          maze[current.row+1][current.col].parentRow = current.row;
                          maze[current.row+1][current.col].parentCol = current.col;
                          maze[current.row+1][current.col].visited = true;
                          cout << current.row << " " << current.col << endl;
                          path.push(current);
                          current.row = current.row + 1;
                          ++squaresVisited;
          }

if 2 is part of the binary number (0010 if I believe... not really knowledgeable w/ binary) and the cell 1 row south with the same column has not been visited then do the following code. However, it never makes it to this point!

Thanks again

Figured it out, made a stupid mistake (increased row instead of column).

Sorry for botherin you all =( Next time I'll come back here with a real problem ;p

This article has been dead for over six months. Start a new discussion instead.