# Stacks

• 02-26-2005
Pressure
Stacks
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:

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```
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 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```
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.

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?
• 02-26-2005
quzah
Just push a direction of movement on the stack. Push always in the same order of direction: N, E, S, W. That is to say, if you've moved to a new cell, look north first. If there is a way to go, go that way. If not, check east. If not, check south, if not, check west, if not, you have to backtrack (pop).

It doesn't really matter at all what order you go in, as long as it's a fixed direction. You may want to run through your stack though, to make sure you're not pushing a location you already have.

So, perhaps pushing a pair of coordinates would be better. Consider the following:
Code:

```11111 10001 10101 G0001 1S111```
Now then, there is potential here for you to simply go from start:
3 N, 2 E, 2 S, 2 W, 2 N, ... repeat indefinately.

So here, what you may want to do, is add a check to see if any of the neighboring squares are the goal. If so, immediately go that direction. Combine this with checking to see if you have in fact been here already, will prevent you from running in circles forever.

Quzah.
• 02-26-2005
Pressure
Alright thanks, I'll write the code to see if I run into any problems.
• 02-26-2005
code will look something like this

Code:

```initial call: find_path(start, finish, maze) bool find_path(Stack &path, 2DVector finish, Matrix maze) {     // check if goal was reached   2DVector current_position = path.top();   2DVector next_position;   if(path.top() == finish)     return SUCCESS;   2DVector direction[4] = {(-1, 0), (1, 0), (0,1), (0, -1) }   for(int x = 0; x < 4; ++x) {       next_position = current_position + direction[x];       if(maze(next_position) != 1) {         path.push(next_position);         // the next_position lead to success!!!         if(SUCCESS == find_path(path, finish, maze))           return SUCCESS;       }       // the next_position didnt lead to success - remove it again       path.pop();     }   return FAILED; }```

sry for those who read the previous code - that one was messed up
[/edit]
• 02-26-2005
quzah
Stop posting C++ code on the C board.

Quzah.
• 02-26-2005
sheesh.. its PSEUDO CODE
well it was intended to be it :D
• 02-26-2005
Pressure
It wasn't the code I was having problems with just the concept but I understand it now.
• 02-27-2005
Pressure
I've run into a bit of a problem. It's either something wrong with how I'm reading in the characters or how I'm printing them. Here's the code:

Code:

```void findmaze(char symbol[LENGTH][LENGTH]) {         int row, col;         for(row = 0; row < LENGTH; row++)                 for(col = 0; col < LENGTH; col++)                         symbol[row][col] = getc(infile);                                 for(row = 0; row < LENGTH; row++)                 for(col = 0; col < LENGTH; col++)                         putchar(symbol[row][col]); }```
When I run the function here's the output I get:

Code:

```11111111111111111111 11111S01111111101111 11111101111111101111 11111100000000001111 11111110111111101111 11111110111111101111 11111110111111101111 11111111111111101111 11111111110000001111 11111111110111101111 11111111110111101111 11111111110111101111 11111111111111101111 11111111111111101111 11111G11111111101111 11111011111111101111 11111000000000001111 11111111111111111111 1111```
Here's the output I want:

Code:

```11111111111111111111 11111S01111111101111 11111101111111101111 11111100000000001111 11111110111111101111 11111110111111101111 11111110111111101111 11111111111111101111 11111111110000001111 11111111110111101111 11111111110111101111 11111111110111101111 11111111111111101111 11111111111111101111 11111G11111111101111 11111011111111101111 11111000000000001111 11111111111111111111 11111111111111111111 11111111111111111111```
You can see how it cuts off the last row and part of the one above it. Why is it doing that? I've tried changing the code around but everything else seems to make it worse.
• 02-27-2005
quzah
Is this a text file, where each "ROW" of your maze is on a seperate line? If so, you're forgetting about the newline that's in the file. You should read that and display it. See, you don't have anything in your code to pay attention to the newline, or to actually display a newline when you are trying to output it.

Quzah.
• 02-27-2005
Pressure
That doesn't seem to be working either or I'm doing it terribly wrong lol. Here's the new updated code:

Code:

```void findmaze(char symbol[LENGTH][LENGTH]) {         int row, col;         for(row = 0; row < LENGTH; row++){                 for(col = 0; col < LENGTH; col++)                         symbol[row][col] = getc(infile);                                         getc(infile);         }                                 for(row = 0; row < LENGTH; row++){                 for(col = 0; col < LENGTH; col++)                         putchar(symbol[row][col]);                                         putchar('\n');         } }```
That should take the end line off after it gets the 20 characters from each line but it doesn't. Here's the output I get:

Code:

```11111111111111111111 11111S0111111110111 111111011111111011 1 11111100000000001 11 1111111011111110 111 111111101111111 1111 11111110111111 01111 1111111111111 101111 111111111100 0001111 11111111110 11101111 1111111111 111101111 111111111 0111101111 11111111 11111101111 1111111 111111101111 11111G 1111111101111 11111 11111111101111 1111 000000000001111 111 1111111111111111 11 11111111111111111 1```
I don't see why it shouldn't work.