I'm just learning the concept of stacks and I'm having a bit of trouble trying to figure out how to use them. I understand that you push values into the stack and you pop the upper most one. It's implementing them that I'm having some issues with.
I have an assignment to do and I need to find my way through a maze using stacks. There are five different symbols I'm using, S is for the start point, G is for the goal, 0 is for the paths, 1 is for the walls and V is for the visited paths.
I already have to code for the stack written but I can't figure out what order to check the paths for the maze in. Here I'll show you what I mean, here's a sample maze:
Now I want to get from S to G by using the stack. In the stack I want to push the x and y coordinates. That's the easy part though, I can already do that. The problem is trying to find the path. When pushing the coordinates into the stack would I want to start with S or G or some 0? Now after pushing in the initial value would I want to check all 4 values around it to see if they're 0's and push them or just push a certain 0? I've been trying to figure out a method to get it to go to G but it's hard to understand using the stack. At the end this is what I'm supose to get:Code:1 1 1 1 1 1 1 1 1 1 1 S 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 G 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
The V means that that 0 has been visited already. I'm supose to use back tracking so if I hit a dead end I go back to the last known area where I can travel down a new path.Code:1 1 1 1 1 1 1 1 1 1 1 S v 1 1 1 1 1 1 1 1 1 v v 1 1 1 1 1 1 1 1 1 v v v v 1 1 1 1 1 1 v 1 1 1 1 1 1 1 1 1 v 1 1 1 1 1 1 1 1 1 v v v G 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
What I'm thinking is that I should start with the G and push the coordinates of that into the stack first. Then I should check the symbols in this order: up , down, left, right. If there is a 0 it should push that symbol's coordinates into the stack then check around that symbol. If I hit a dead end I should pop the coordinates until I reach a V with a 0 next to it. I should continue doing that until I reach the S. Do you think that would work?