Issue solving Maze with Backtrack

Question

I have a project that receive a maze via txt file, and I have to solve it. The only hard specifications to solve it is: No other Bi-dimensional Array (No Copy, No Bool).

So I use stacks and backtracking to solve it. I use two stacks, one to copy the visited rooms, and the other one to copy the path. But the thing is that when I'm back to the main function, the two stacks only got the last position they got in the maze. So that's my problem, just got the last position in my stacks.

When I'm in the Backtracking Function, there's another function that check if I was in that position before, I test the stack I mentioned before, and works fine( the stack that save the visited rooms), I printed all values of this stack.

I don't know why the main function can't receive the full stack (at least for the visited rooms), the path stack its not working at all.

bool path(ColaD* colaDG, Node* temp, PileD* pileDG)
{
    if (temp->row == colaDG->end->row && temp->col == colaDG->end->col)
        return true;
    if (check(pileDG, temp) || mat[temp->row][temp->col] == 1)
    {
        // call check function
        return false;
    }
    pileDG->push(*temp);
    if (temp->row != 0)
    {
        temp->row -= 1;
        colaDG->push(*temp);
        if (path(colaDG, temp, pilaDG))
        {
            return true;
        }
        temp->row += 1;
    }
    if (temp->row != n - 1)
    {
        temp->row += 1;
        colaDG->push(*temp);
        if (path(colaDG, temp, pilaDG))
        {
            return true;
        }
        temp->row -= 1;
    }
    if (temp->col != 0)
    {
        temp->col -= 1;
        colaDG->push(*temp);
        if (path(colaDG, temp, pilaDG))
        {
            return true;
        }
        temp->col += 1;
    }
    if (temp->col != m - 1)
    {
        temp->col += 1;
        colaDG->push(*temp);
        if (path(colaDG, temp, pilaDG))
        {
            return true;
        }
        temp->col -= 1;
    }
    return false;
}
bool check(PileD* pileDG, Node* temp)
{
    // Function to check visited rooms
    bool flag = false;
    Node * recor;
    recor = new Node();
    recor = pileDG->top;
    while (recor != NULL)
    {
        if (recor->row == temp->row && recor->col == temp->col)
        {
            // if already here, return true
            flag = true;
            break;
        }
        else
            recor = recor->pre;
    }
    return flag;
}

I have to change the Path Stack, I know, but is not working anyways.

I think about using graph to solve it, but I don't know how to implement a graph at all. Sorry for my English, I'm not a native English speaker. I tried to change some words to the code, cause some words were in Spanish. Any help would be great. And sorry for the whole code in the .cpp file, I'm just testing, the real project will be different.

Full Code:

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

int n=0,m=0;
int **mat;

class Node{
public:
        Node(){pre=NULL;}
        int row;
        int col;
        Node *pre;
};

class ColaD{
   public:
        ColaD(){fin=fte=end=NULL;}
        void push(Nodo xdato);
        void pop();
        Node *fte,*fin,*end;
};
void ColaD::push(Node xdato){
     Node *nuevo;
     nuevo = new Node();
     if(nuevo){
          (*nuevo)= xdato;
          nuevo->pre = NULL;
          if(!fte)
             fte = nuevo;
          else
             fin->pre=nuevo;
          fin = nuevo;
     }
}
void ColaD::pop(){
     Node *elim; 
     if(fte){
        elim = fte;
        if(fte==fin)
           fte = fin = NULL;
        else
            fte = fte->pre;
        delete(elim);
     }
}
class PileD{
   public:
        PileD(){tope=NULL;}
        void push(Node xdato);
        void pop();
        Node *tope;
};
void PilaD::push(Node xdato){
        Node *nuevo;
        nuevo = new Node;
        if(nuevo){
          (*nuevo)=xdato;
          nuevo->pre=tope;
          tope=nuevo;
        }
}
void PileD::pop(){
        Node *aux;
        if(tope){
          aux=tope;
          tope=tope->pre;
          free(aux);    
        }
}

void tamMat(); //read the size of the maze given by a txt file
void loadM(); //once i know the size, and the bi dimensional is created I set the values to de bi dimensional A.
void printM(); //Just check the values
bool path(ColaD *colaDG,Node *temp,PileD *pileDG); 
bool check(PileD *pileDG,Node *temp);


int main(int argc, char const *argv[])
{
        ColaD *colaDG;
        Node *inicio;
        PileD *pileDG;
        tamMat();  //Read the size
        mat = new int*[n];
        for(int i=0;i<n;i++)
         mat[i]=new int[m];

    loadM(); //Set values given from the file
    colaDG = new ColaD();
    pileDG = new PileD();
    inicio = new Node();
    inicio->row=0;  //Proyect says, the start of the maze is in the first row of the maze
    for(int j=0;j<m;j++)
        if(mat[0][j]!=1){
                inicio->col=j; //Found the position in the row
                break;
            }
    colaDG->end = new Nodo();
    colaDG->end->row=n-1; //End position is in the last row
    for(int j=0;j<m;j++)
        if(mat[n-1][j]!=1){
                colaDG->end->col=j; //Found the position
                break;
            }
        bool b = path(colaDG,inicio,pilaDG); //call my backtrack function
        getchar();
        /* CODE TO CHECK visited Rooms
        Nodo *temp = new Nodo();
        temp=pileDG->tope;
        while(temp!=NULL){
            cout << temp->row <<" "<<temp->col << endl;
            getchar();
            temp->pre;                         
        }
        */
        getchar();

        return 0;
}

void tamMat(){ 
        fstream inFile;
        int num;
        n=m=0;
        inFile.open("mat.txt",ios::in);
        string line;

        getline(inFile,line);
        stringstream temp(line);
        while(temp>> num)
                m++;
        n++;
        while(getline(inFile,line))
                n++;
        inFile.close();
}
void loadM(){
        fstream inFile;
        inFile.open("mat.txt",ios::in);
        for(int i=0;i<n;i++)
                for(int j=0;j<m;j++)
                        inFile >> mat[i][j];
        inFile.close();
}

void printM(){
        for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
           if(mat[i][j]!=1)
                         cout << " ";
           else
             cout << mat[i][j];
           cout << " ";
        }
                cout << endl;
        }
}
bool path(ColaD *colaDG,Node *temp,PileD *pileDG){

    if(temp->row==colaDG->end->row && temp->col==colaDG->end->col) return true;
    if(check(pileDG,temp) || mat[temp->row][temp->col]==1){
          return false;      
    }
    pileDG->insertar(*temp);
    if(temp->row!=0){
         temp->row-=1;
         colaDG->insertar(*temp);            
         if(path(colaDG,temp,pileDG)){
              return true;
         }
         temp->row+=1;
    }
    if(temp->row!=n-1){
         temp->row+=1;
         colaDG->insertar(*temp);
         if(path(colaDG,temp,pileDG)){
              return true;
         }
         temp->row-=1;          
    }
    if(temp->col!=0){
         temp->col-=1;
         colaDG->insertar(*temp);
         if(path(colaDG,temp,pileDG)){
              return true;
         }
         temp->col+=1;    
    }
    if(temp->col!=m-1){     
         temp->col+=1;
         colaDG->insertar(*temp);
         if(path(colaDG,temp,pileDG)){
              return true;
         }
         temp->col-=1;       
    }
    return false;
}
bool check(PileD *pileDG,Node *temp){
     bool flag=false;
     Node *recor;
     recor = new Node();
     recor = pileDG->tope;
     while(recor!=NULL){
          if(recor->row==temp->row && recor->col==temp->col){
              flag=true;
              break;
          }
          else
              recor=recor->pre;
     }
     return flag;
}

Maze mat.txt file.

0 0 0 1 1 1 1 1 1 1
1 1 0 1 0 5 1 1 0 1
1 1 6 1 7 1 1 1 0 1
1 1 0 1 0 1 0 0 0 1
1 0 9 0 0 1 0 1 0 1
1 8 1 1 0 1 6 1 0 1
1 0 1 1 0 1 0 1 5 1
1 0 1 1 0 1 0 1 0 1
1 0 0 1 0 0 0 1 7 1
1 1 1 1 1 1 1 1 0 1

1=Walls / 0=Free Space / Other numbers = Bonus

Answer 1

There are many problems with your code, some of them are important, some are just efficiency issues. The main problem I can see now is not in your analysis code but rather in your diagnostics code.

Look at the part in comment:

    /* CODE TO CHECK visited Rooms */
    Nodo *temp = new Nodo();
    temp=pileDG->tope;
    while(temp!=NULL){
        cout << temp->row <<" "<<temp->col << endl;
        getchar();
        temp->pre;
    }

The last line before the closing brace is

        temp->pre;

It just reads the pre field from *temp object, but does not use that value – the temp variable is not modified, so the program stays in the loop forever, printing again and again the same piece of data.

I guess

        temp = temp->pre;

is what you meant.

Anyway such loops are easier to write and to read if you use for instead of while:

    /* CODE TO CHECK visited Rooms */
    for( Nodo *temp=pileDG->tope; temp!=NULL; temp=temp->pre){
        cout << temp->row <<" "<<temp->col << endl;
        getchar();
    }

Once you replace it you will possibly see (some of) other problems with the code. For example you may find too many 'visited' positions in the output printed.

Answer 2

What happens in this part of code?

Node * recor;
recor = new Node();
recor = pileDG->top;

Isn't the new node lost forever...?

You seem to place every new point visited onto the colaDG stack. I can't see however where you remove the points when you track back from dead-end paths...