I just want to ask something about using a stack in maze
Im confused about implementing stack in c++.is it possible that I can insert a multidimensional array in a stack,how?:S
(can you please give me some little bit of codes in order to do that)
I did already a maze using a recursion,but the requirements have been changed by my prof...it should have no recursion and uses a stack to store the coordinates
I just want to ask something about using a stack in maze
Im confused about implementing stack in c++.is it possible that I can insert a multidimensional array in a stack,how?:S
(can you please give me some little bit of codes in order to do that)I did already a maze using a recursion,but the requirements have been changed by my prof...it should have no recursion and uses a stack to store the coordinates
Just about everything is possible in C++. You can use a stack with any type, including a multidimensional array. But your question is too vague to answer, in my opinion. You have some sort of maze assignment, which could be any number of things. Are you designing a maze, solving a maze, what?
Im trying to solve the maze
Im trying to solve the maze
That clarifies things, but not by much. What's the question? How to implement a maze solving algorithm that doesn't use recursion? How to use a stack, independent of the fact that you are using it to solve a maze? What's a good algorithm to solve the maze? No one can help you if you don't get more specific. What is the assignment, what have you done, what do you know how to do already, what are you stuck on?
Whats the actual question? A stack really doesn't take any implementing, non-dynamic (ie stack) variables are handled automatically (pushed and popped). There is a stack in the stl...but it's really not that useful...
hey guys Im new here in this forum
sorry for posting lame question here and bad grammar?
my question really is
1. I need an idea how to solve a maze without using recursion (thats a algorithm)and
2 the stack is involve in this,(this one will store the paths that have been visited in the maze)
Im poor at c++ but I know some basic stuff in c++..
the maze comes from a text file,
There is a stack in the stl...but it's really not that useful..
honestly I dont know that...but I need to do that stuff.
This is most of the general containers in C++: http://www.cplusplus.com/reference/stl/
Stack is sort of useless, for this.
Stack is sort of useless, for this.
I disagree with you on this one, I think. I'm not sure it is the best way, but I think it could come in handy. The devil is in the details, obviously, and there are numerous ways to solve a maze, but perhaps the idea is to have a whole bunch of 2-D mazes (one for each move through the maze). As you move, you do a deep copy of the 2-D maze, change your position, and push it onto the stack. Hit a dead end, start popping off the stack to get to where you were before. Again, possibly not the best approach, there's an awful lot of memory being used, but it could be useful and doable. That's my best guess of what the teacher intends.
1. I need an idea how to solve a maze without using recursion (thats a algorithm)and
2 the stack is involve in this,(this one will store the paths that have been visited in the maze)
Im poor at c++ but I know some basic stuff in c++..
the maze comes from a text file,
Best, simplest, brute force approach (tried and true) is to always keep a wall on your right. It's the same algorithm as the recursive algorithm. Hug the right wall with your right hand, never let go of a wall, follow wherever your right hand takes you.
More detailed advice can't be given till you yourself post something much more detailed. For example, you haven't posted at all what this 2-D array is composed of and how it changes as you traverse the maze. If you already have decided that, you need to post it originally. If not, you need to think about it.
Here's what I would do for something like this. Pick a direction to be the base direction. Now always move in this direction unless theres a wall in the way, if there is, try to change direction (except the way you came from). Everytime you come to an intersection (more than one possible path) push that location into a vector (not a stack). (This will probably require that you make a struct called coords containing a x and y member and also a member indicating the number of available paths, and the number of paths already checked). Now every time you come to a dead end, revert to the last location, and increment the paths already checked. If this reaches total paths available (all paths checked) then revert back to the intersection previous to that. Also note, to avoid some strange errors, a check to make sure that if there is a loop in the maze, bringing you back to the same intersection, that you just call that a failure also (revert back to last intersection). This might seem a bit complicated, but is the most optimized method I can think of.
@skatamatic thanks for the idea
,the stack will be the one who will store the paths and I want the program to not use recursion,how can I do that in this program?
a similar algorithm for this one is listed below,but what I did is so different from this algo
Find the starting point
look for the letters along the border of your maze
while stack is not empty
pop stack,store it in a variable as current row and column except for visited path
check for a path on all sides ofthe current postion
if there is path,push it in the stack
loop
#include <stdlib.h> // allows use of = clrscreen();
#include <conio.h>
#include <fstream>
#include <iostream.h>
#include <iomanip>
#include <stack.h>
#include "clear.h"
using namespace std;
void Traverse( char[][80], int, int, int);
void Maze(const char[][80]);
bool validmove(const char[][80],int,int);
bool Edge (int,int);
enum direction {DOWN,RIGHT,UP,LEFT}; //0,1,2,3
const int x = 2;
const int y = 0;
////****Main****////
void pushX(int);
void pushY(int);
stack< int > s;
int main()
{
char maze[25][80];
ifstream infile;
infile.open("25X80_1.txt");
for (int i = 0; i < 25; i++) {
for (int j = 0; j < 80; j++) {
infile>>maze[i][j];
}
//cout<<'\n';
}
Traverse(maze,x,y,RIGHT);
system("PAUSE");
return 0;
}
void Traverse(char maze[][80], int xlocation, int ylocation, int direction)
{
maze[xlocation][ylocation]='Ü';
cout<<"Determining current state "<<endl<<"Array";
pushX(xlocation);
pushY(ylocation);
cout<<endl<<endl;
//popY(ylocation);
// popX(xlocation);
cout<<endl<<endl;
Maze(maze);
clrscreen();
// pushArray();
if (Edge(xlocation,ylocation) && xlocation!=x && ylocation!=y)
{
cout<<"Maze game SOLVED!!! \n";
return;
}
else {
for (int move =direction,count=0;count<4;count++,move++,move%=4)
switch (move)
{
case DOWN:
if ( validmove(maze,xlocation+1,ylocation) )
{
Traverse(maze,xlocation+1,ylocation,LEFT);
return;
}
break;
case RIGHT:
if (validmove(maze,xlocation,ylocation+1))
{
Traverse(maze,xlocation,ylocation+1,DOWN);
return;
}
break;
case UP:
if (validmove(maze,xlocation-1,ylocation))
{
Traverse(maze,xlocation-1,ylocation,RIGHT);
return;
}
break;
case LEFT:
if (validmove(maze,xlocation,ylocation-1))
{
Traverse(maze,xlocation,ylocation-1,UP);
return;
}
break;
} //end switch
} //end for loop
} //end Travers function
bool validmove(const char maze[][80],int r, int c)
{
return (r>=0 && r<=24 && c>=0 && c<=79 && maze[r][c]!='*');
}
bool Edge(int x ,int y)
{
if ((x==0||x==24)&&(y>=0&&y<=79))
return true;
else if ((y==0||y==79)&&(x>=0&&x<=24))
return true;
else
return false;
}
void Maze(const char maze[][80]) {
for (int x=0;x<25;x++) {
for (int y=0;y<80;y++) {
cout<<maze[x][y];
}
cout<<'\n';
}
// cout<<"Press Enter for the next move\n";
cin.get();
}
void pushX(int x ){ //push row
s.push( x );
cout <<"["<<s.top()<<"]";
}
void pushY(int y ){ //push column
s.push( y );
cout <<"["<<s.top()<<"]";
}the Traverse() is in a recursive way,but I want someone to make all this code in a procedural way(dont know what's the right term ) and it uses a stack,
,the stack will be the one who will store the paths and I want the program to not use recursion,how can I do that in this program?
the Traverse() is in a recursive way,but I want someone to make all this code in a procedural way(dont know what's the right term ) and it uses a stack,
That someone is you. We're here to help, not do it for you. Who wrote the code above? Do you understand it?
,the stack will be the one who will store the paths and I want the program to not use recursion,how can I do that in this program?
a similar algorithm for this one is listed below,but what I did is so different from this algo
Find the starting point
look for the letters along the border of your maze
while stack is not empty
pop stack,store it in a variable as current row and column except for visited path
check for a path on all sides ofthe current postion
if there is path,push it in the stack
loop...
the Traverse() is in a recursive way,but I want someone to make all this code in a procedural way(dont know what's the right term ) and it uses a stack,
Do you really expect someone to rewrite all that code? I mean...would you be willing to do that for someone else? People get paid big bucks for things like that. Also, did you write that code? The indentation and whitespace is terrible, and you should post with [ code = cplusplus ] (minus all spaces) for syntax highlighting. Most people, including myself, won't even read something like that.
but I want someone to make all this code in a procedural way
what i mean is the pseudocode or maybe an algo?strike 2 for me,for not being specific again,haha,my mistake
I know and understand the code,syntax was bad,Im in a hurry,I got now the solution,this post can now be closed because I got it all now covered.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.