This is my first Question on stack overflow and it is for my homework. What I have to do is find all the possible paths from start to end. What I am doing is that I am calling the function if it finds '-' and the parameters for the function are the indexes on which '-' is. The current parameters are pushed on stack. Before explaining further I want to show the output and the maze.
5 6
s - - - - -
- * * * * -
- * * * * -
- * * * * -
- - - - - e
The starting two ints are rows and cols.
00,01,11,21,22,02,03,13,23,22,04,05,15,25,35,45,44,43,42,32,22
Output is taken out from the stack.
To some extent the output is correct as you can see the function is traversing every path. What I am unable to do is keep track of function and why I want to do this? Because I want to print all the paths from start (0, 0 in this case). How can I keep track of the function when it has two paths to traverse so that I can print it from the starting index?
00,01,11,21,22
00,01,02,03,13,23,22
00,01,02,03,04,05,15,25,35,45,44,43,42,32,22
I'll provide code also If necessary. I have Edited Code . I am pushing indexes (1,0)on stack like first 0 then 1 and popping two as well in order to remove it . I have understanding why my output is like this (mentioned above ) because , take example of the maze in program at (0,0) it have two options either go up or down . it goes down and because all these statements are if not if else program after function execution does check other conditions so it goes to its other option which is right . Okay so what about the Output? all the indexes are pushed on stack and when 'e' is found it prints all the indexes stored but it does not remove them . for this example I can pop everything from the stack after printing and the outputs will be fine (not repeating) take another example
6 6 s 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 1 e
In this Example you can see it has two options at (0,2) so I cannot pop everything from stack here after first path end is reached . because it will pop (0,0) and (0,1) as well . what I want is to pop only until (0,2)
That is what I am trying to do .
#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
ofstream fout("Q1(output).txt");
ifstream fin("Q1.txt");
class stack
{
private:
int row,col;
int top;
string str;
int sourceA,sourceB,destinationA,destinationB;
char **store;//arr which has maze is passed into class . 'store' has maze.
public:
stack(int row,int col)//constructor , paramerters are rows and cols
{
this->row=row;
this->col=col;
top=-1;
sourceA=0;
sourceB=0;
}
void finish()
{
while(top!=-1)
{
top--;
}
}
void push(int dataA,int dataB )//push two indexes in str like (0,1) pushed as first 0 then 1
{
if(top==-1)
{
top++;
str[top]=dataA ;
top++;
str[top]=dataB ;
}
else
{
top++;
str[top]='1';
top++;
str[top]=dataA ;
top++;
str[top]=dataB ;
}
}
void pop(int varA ,int varB)//This function was made for other purpose but not used
{
for(int a=0;a<top+1;a++)
{
if(a==varA && a+1==varB )
{
top=a-2;
cout<<top;
}
}
cout<<endl;
}
int ret()
{
return top;
}
void empty()
{
if(top==-1)
cout<<"\nEmpty\n";
else
cout<<"\nNot Empty\n";
}
void get(char **arr)// saving arr(Maze) into store
{
char ch;
store=NULL;
store=new char*[row];
for(int a=0;a<row;a++)
{
store[a]=new char[col];
for(int b=0;b<col;b++)
{
store[a][b]=arr[a][b];
cout<<store[a][b];
if(arr[a][b]=='s')
{
sourceA=a;//saving the 's' index , my inititate starts from here .
sourceB=b;
}
else if(arr[a][b]=='e')
{
destinationA=a;//saving the 'e' index , used later.
destinationB=b;
}
}
cout<<endl;
}
}
int getA()
{
return sourceA;
}
int getB()
{
return sourceB;
}
int getAD()
{
return destinationA;
}
int getBD()
{
return destinationB;
}
int initiate(int a,int b)
{
int tempA,tempB;
push(a,b);
if(a>0 )
{
if(store[a-1][b]=='1'&&store[a-1][b]!='v')
{
store[a][b]='v';
initiate(a-1,b);
store[a][b]='1' ;
}
}
if(b>0 )
{
if(store[a][b-1]=='1'&&store[a][b-1]!='v')
{
store[a][b]='v';
initiate(a,b-1);
store[a][b]='1' ;
}
}
if(a!=row-1)
{
if(store[a+1][b]=='1'&&store[a+1][b]!='v')
{
store[a][b]='v';
initiate(a+1,b);
store[a][b]='1' ;
}
}
if(b!=col-1)
{
if(store[a][b+1]=='1'&&store[a][b+1]!='v')
{
store[a][b]='v';
initiate(a,b+1);
store[a][b]='1' ;
}
}
if(a+1==destinationA && b==destinationB ||a-1==destinationA && b==destinationB ||a==destinationA && b+1==destinationB ||a==destinationA && b-1==destinationB )
{
push(destinationA,destinationB);
cout<<"\nPath : \n";
print1();
}
pop();
}
void print1()
{
for(int a=0;a<top+1;a++)
{
if(str[a]!='1')
{
int ret=str[a];
cout<<ret;
fout<<ret;
}
else
{
cout<<endl;
fout<<endl;
}
}
fout.close();
}
int pop()
{
int ret=str[top];
top--;
int ret1=str[top];
top--;
}
void show()
{
cout<<endl<<endl;
for(int a=0;a<row;a++)
{
for(int b=0;b<col;b++)
{
cout<<store[a][b];
}
cout<<endl;
}
}
};
main()
{
char ch;
int row,col;
fin >> row;
fin >> col;
stack s(row,col);
char **arr=NULL;
arr=new char*[row];
for(int a=0;a<row;a++)
{
arr[a]=new char[col];
for(int b=0;b<col;b++)
{
fin>>ch;
arr[a][b]=ch;
}
}
fin.close();
s.get(arr);
s.initiate(s.getA(),s.getB());
s.show();
exit(1);
}
Printing all paths can be done using recursion as you're doing, but you'll need to keep track of the path you've taken to reach the goal and either print it upon each arrival at the destination or save it in a container. I prefer the latter approach. The path can be a stack or other structure that supports push/pop operations. Each node you visit in your traversal should be added to the path and popped once all of its neighbors have been fully expanded.
Here's the recursive path-building algorithm in pseudocode:
function DFS(row: int, col: int, maze: char[][], path: int[][], result: int[][][]) {
path.push([row, col])
if ([row, col] is the destination) {
result.add(path)
}
else {
for (direction in each_cardinal_direction) {
new_row = row + direction.row
new_col = col + direction.col
if (in_bounds(new_row) and in_bounds(new_col) and
maze[new_row][new_col] is unvisited) {
maze[row][col] = visited
DFS(new_row, new_col, maze, path, result)
maze[row][col] = unvisited
}
}
}
path.pop()
}
It's not entirely clear to me why you're using both explicit and implicit state; usually, when running a DFS, use an explicit stack and a while loop or use recursion and store all state as frames on the call stack. Consider improving naming clarity, design and spacing/indentation so your logic is easier to follow.
For example, str is an array that acts as a stack and should be named as such, while your stack class isn't actually a stack at all, but rather a maze solver. Your pop functions aren't accurate and should only remove one element at a time.
Additionally, since you're using C++ classes and strings, you may as well take advantage of containers as well.
Here's a recursive example which modifies the maze temporarily, adding walls to mark visited nodes to avoid cycles:
#include <iostream>
#include <vector>
void DFS(
int row, int col,
std::vector<std::vector<char>> &maze,
std::vector<std::pair<int, int>> &path,
std::vector<std::vector<std::pair<int, int>>> &result
) {
path.push_back(std::make_pair(row, col));
if (maze[row][col] == 'e') {
result.push_back(path);
}
else {
int dirs[][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
for (auto d : dirs) {
int r = d[0] + row;
int c = d[1] + col;
if (r >= 0 && c >= 0 && r < maze.size() &&
c < maze[r].size() && maze[r][c] != '*') {
maze[row][col] = '*';
DFS(r, c, maze, path, result);
maze[row][col] = '-';
}
}
}
path.pop_back();
}
std::vector<std::vector<std::pair<int, int>>>
getPaths(std::vector<std::vector<char>> maze) {
std::vector<std::vector<std::pair<int, int>>> result;
std::vector<std::pair<int, int>> path;
int row = -1;
int col = -1;
for (int i = 0; i < maze.size() && row == -1; i++) {
for (int j = 0; j < maze[i].size() && col == -1; j++) {
if (maze[i][j] == 's') {
row = i;
col = j;
}
}
}
DFS(row, col, maze, path, result);
return result;
}
int main() {
std::string raw = "s-----\n*-*-*-\n*-e-*-\n**-**-\n**----";
std::vector<std::vector<char>> maze;
std::vector<char> row;
for (int i = 0; i < raw.size(); i++) {
if (raw[i] == '\n') {
maze.push_back(row);
row.clear();
}
else {
row.push_back(raw[i]);
}
}
maze.push_back(row);
for (auto &path : getPaths(maze)) {
std::cout << std::endl << '[';
for (auto &cell : path) {
std::cout << '(' << cell.first <<
"," << cell.second << ')';
}
std::cout << ']' << std::endl;
}
}
Output:
[(0,0)(0,1)(0,2)(0,3)(0,4)(0,5)(1,5)(2,5)(3,5)(4,5)(4,4)(4,3)(4,2)(3,2)(2,2)]
[(0,0)(0,1)(0,2)(0,3)(1,3)(2,3)(2,2)]
[(0,0)(0,1)(1,1)(2,1)(2,2)]