# Recording a maze path solution with a stack

I am to generate a solution to a maze using a linked list implementation of a stack in some way. The maze is read in from a .txt file and consists of 0's for open spaces and 1's for walls. <- Pretty sure an exit must be in the bottom row? So those three 0's?

The algorithm I am attempting to use is:

```While Not At End
If Can Go North
Go North
ElseIf Can Go East
Go East
ElseIf Can Go South
Go South
ElseIf Can Go West
Go West
EndIf
Wend
```

The way I've been attempting it relied on the ++ operations executing within an array index. I was unaware the array subscript operator [ took precedence over ++ so now I need to rethink a work around. Before doing so, I want to make sure this method will even work in first place. Could anyone take a look at my algo code thus far and provide some feed back? (Note: I still need to add in some code to track paths taken to avoid some type of infinite loop)

```bool notSolved = true;
int path = 0;
row = 0;
col = 0;

rowStack.push(row);
colStack.push(col);

while (notSolved){

//(from perspective of person looking at maze on screen)
if (maze[row--][col] == 0){//if you can go up, go up
rowStack.push(row);
colStack.push(col);
path++;
}
else if (maze[row][col++] == 0){//else if you can go right, go right
rowStack.push(row);
colStack.push(col);
path++;
}
else if (maze[row++][col] == 0){//else if you can go down, go down
rowStack.push(row);
colStack.push(col);
path++;
}
else if (maze[row][col--] == 0){//else if you can go left, go left
rowStack.push(row);
colStack.push(col);
path++;
}

if((maze[row][col] == 0) && (row == (size - 1))){//if we reached an exit
cout << "Solution Path:" << endl;
for (int i = 0; i < path; i++){
cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl;
rowStack.pop();
colStack.pop();
}
notSolved = false;
}
}
```

Problem with executing [ before ++:

Any help appreciated, Thanks!

Your algorithm will not work in certain mazes that have circular paths: once you get into one of these, you'll be going in circles. To fix this, you need to add a boolean array visited[R][C][DIR], where DIR is a number from zero to three representing a direction. When you leave cell [r][c] in the direction [d], set visited[r][c][d] to true. Next time you visit the same cell, see if you have left it in the same direction before; if you did, skip that direction, and go for the next one down the line.