Question

Need to program a maze traversal program using dynamic array and stacks. The problem is faced in setting up the data structure and due the problem in setting the data structure other functions like moving in all direction, marking the current cell that is visited are showing the error.

The work so far is below:

const int R = 5; //Number of rows
const int C = 5; //Number of columns

class coordinate
{
public:
int v;
int h;
};

class stack
{
public:
coordinate x;
coordinate y;
};

The maze looks like:

# # S _ #

_ _ _ # #

_ # # _ #

_ _ # # #

_ _ _ _ G

where S = starting point, G = end point, _ = space for moving around and # = wall

Answer 1

// Java program to solve maze traversal program
// problem with dynamic array and stacks
import java.util.Stack;
  
class Node
{
private int x, y;
private int dir;
  
public Node(int i, int j)
{
this.x = i;
this.y = j;
  
// default value for direction set to 0 (Up)
this.dir = 0;
}
  
public int getX()
{
return x;
}
  
public void setX(int x)
{
this.x = x;
}
  
public int getY()
{
return y;
}
  
public void setY(int y)
{
this.y = y;
}
  
public int getDir()
{
return dir;
}
  
public void setDir(int dir)
{
this.dir = dir;
}
}
  
public class MazeTravel
{
private static final int R = 5;
private static final int C = 5;
public static String out="";
  
// maze of n*m matrix
int n = R, m = C;
  
private static boolean[][] visited = new boolean[R][C];
  
// Driver code
public static void main(String[] args)
{
// Initially setting the visited
// array to true (unvisited)
setVisited(true);
  
// Maze matrix
char maze[][] = {{ '#', '#', 'S', '_', '#' },
{ '_', '_', '_', '#', '#' },
{ '_', '#', '#', '_', '#' },
{ '_', '_', '#', '#', '#' },
                       { '_', '_', '_', '_', 'G' }};
                      
       for (int k = 0; k < maze.length   ; k++)
{
for (int l = 0; l < maze[k].length; l++)
{
System.out.print(maze[k][l]+"\t");
}
System.out.println();
}
  
if (isReachable(maze))
{
System.out.println("Path Found!\n");
System.out.println(out.substring(0,out.length()-4)+"Goal");
  
}
else
System.out.println("No Path Found!\n");
}
  
private static void setVisited(boolean b)
{
for (int i = 0; i < visited.length; i++)
{
for (int j = 0; j < visited[i].length; j++)
{
visited[i][j] = b;
}
}
  
}
  
private static boolean isReachable(char maze[][])
{
// Initially starting at S.
  
int i=0, j=0;
       for (int k = 0; k < maze.length; k++)
{
for (int l = 0; l < maze[k].length; l++)
{
if(maze[k][l] == 'S'){
                   i=k;
                   j=l;
               }
}
}
System.out.println("Start coordinates: " + i + ", " + j);
// Goal coordinates
// Coordinates of Goal
int fx=R, fy=C;
       for (int k = 0; k < maze.length   ; k++)
{
for (int l = 0; l < maze[k].length; l++)
{
if(maze[k][l] == 'G'){
                   fx=k;
                   fy=l;
               }
}
}
System.out.println("Goal coordinates: " + fx + ", " + fy);
Stack<Node> s = new Stack<Node>();
  
Node temp = new Node(i, j);
  
out = out + "Start("+(i)+" ,"+(j)+") -> ";
  
s.push(temp);
  
while (!s.empty())
{
  
// Pop the top node and move to the
// left, right, top, down or retract
// back according the value of node's
// dir variable.
temp = s.peek();
int d = temp.getDir();
i = temp.getX();
j = temp.getY();
  
// Increment the direction and
// push the node in the stack again.
temp.setDir(temp.getDir() + 1);
s.pop();
s.push(temp);
  
// If we reach the Food coordinates
// return true
if (i == fx && j == fy)
{
return true;
}
  
if (d == 0)
{
// Checking the Up direction.
if (i - 1 >= 0 && (maze[i - 1][j] == '_' || maze[i - 1][j] == 'G') &&
visited[i - 1][j])
{
Node temp1 = new Node(i - 1, j);
visited[i - 1][j] = false;
out = out + "("+(i - 1)+" ,"+(j)+") -> ";
s.push(temp1);
}
}
else if (d == 1)
{
// Checking the left direction
if (j - 1 >= 0 && (maze[i][j-1] == '_' || maze[i][j-1] == 'G') &&
visited[i][j - 1])
{
Node temp1 = new Node(i, j - 1);
visited[i][j - 1] = false;
out = out + "("+(i)+" ,"+(j-1)+") -> ";
s.push(temp1);
}
}
else if (d == 2)
{
// Checking the down direction
if (i + 1 < R && (maze[i + 1][j] == '_' || maze[i + 1][j] == 'G') &&
visited[i + 1][j])
{
Node temp1 = new Node(i + 1, j);
visited[i + 1][j] = false;
out = out + "("+(i + 1)+" ,"+(j)+") -> ";
s.push(temp1);
}
}
else if (d == 3)
{
// Checking the right direction
if (j + 1 < C && (maze[i][j+1] == '_' || maze[i][j+1] == 'G') &&
visited[i][j + 1])
{
Node temp1 = new Node(i, j + 1);
visited[i][j + 1] = false;
out = out + "("+(i)+" ,"+(j+1)+") -> ";
s.push(temp1);
}
}
  
// If none of the direction can take
// the rat to the Food, retract back
// to the path where the rat came from.
else
{
visited[temp.getX()][temp.getY()] = true;
s.pop();
}
}
  
// If the stack is empty and
// no path is found return false.
return false;
}
}