Number of Ways in a Given maze from start to end

Question

So I am trying to find how many ways exist in a given maze from start to end.

Here is my code, using Depth first search.

import java.util.Stack;

public class NumberofWaysInAMaze {
class VisitedNode
{
    private int x;
    private int y;


    public VisitedNode(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}

public int findNumberofWaysToMaze(boolean[][] maze, int targetX, int targetY)
{
    int numberofWays = 0;
    int rows = maze.length;
    int columns = maze[0].length;
    boolean[][] visitedMap = new boolean[rows][columns];
    for(int i=0; i < rows; i++)
    {
        System.arraycopy(maze[i], 0, visitedMap[i], 0, maze[i].length);
    }

    Stack<VisitedNode> stack = new Stack<VisitedNode>();

    VisitedNode root = new VisitedNode(0, 0);
    stack.push(root);

    while(!stack.empty())
    {
        VisitedNode visitingNode = stack.pop();
        int currentX = visitingNode.x;
        int currentY = visitingNode.y;
        if(currentX == targetX && currentY == targetY)
        {
            numberofWays++;
        }else

        {//System.out.println("x is:" + currentX + "--- y is:" + currentY);
        visitedMap[currentX][currentY] = true;
        }
        if(currentX+1 <= targetX && currentX+1 >= 0 && visitedMap[currentX+1][currentY] == false && maze[currentX+1][currentY] == false)
        {
            stack.push(new VisitedNode(currentX+1, currentY));
        }

        if(currentX-1 <= targetX && currentX-1 >= 0 && visitedMap[currentX-1][currentY] == false && maze[currentX-1][currentY] == false)
        {
            stack.push(new VisitedNode(currentX-1, currentY));
        }

        if(currentY+1 <= targetY && currentY+1 >= 0 && visitedMap[currentX][currentY+1] == false && maze[currentX][currentY+1] == false)
        {
            stack.push(new VisitedNode(currentX, currentY+1));
        }

        if(currentY-1 <= targetY && currentY-1 >= 0 && visitedMap[currentX][currentY-1] == false && maze[currentX][currentY-1] == false)
        {
            stack.push(new VisitedNode(currentX, currentY-1));
        }

    }

    return numberofWays;
}

public static void main(String[] args)
{
    NumberofWaysInAMaze test = new NumberofWaysInAMaze();
    boolean[][] maze = 
            {
             {false, false, false, false, false},
             {false, true, false, true, false},
             {false, true, false, true, false},
             {false, true, false, true, false},
             {false, false, false, false, false},
            };
    System.out.println(test.findNumberofWaysToMaze(maze, 4, 4));
}

}

However, the output is not right. My output is 2 and obviously, there are four ways in the given maze(false means OK to pass and true means Block). I know the reason is because I use another 2D array to record whether a point has been visited. However, I don't know how I can modify my solution. Any comments or suggestions would be highly appreciated.

Thanks

Answer 1

You are correct in assuming that your visitedMap is causing problems. The thing is that multiple paths can pass through the same node, so you're getting a result of 2 because there are only two possible positions immediately adjacent to the target.

Unfortunately, your stack as you have implemented it is not capable of unwinding the path of visited points back to what was available at the time each position was added.

This would be much easier for you to implement recursively. When you enter the function, you mark the point at (currentX, currentY) as visited. When you leave the function, you unmark it. That will unwind your path correctly.

Your function would be something like this:

public int findNumberofWaysToMaze( boolean[][] maze, boolean[][] visitedMap,
                                   int currentX, int currentY, int targetX, int targetY )
{
    if( currentX == targetX && currentY == targetY ) return 1;

    if( currentX < 0 || currentX >= maze.length ) return 0;            // X out of bounds
    if( currentY < 0 || currentY >= maze[currentX].length ) return 0;  // Y out of bounds
    if( visitedMap[currentX][currentY] == true ) return 0;             // Already seen
    if( maze[currentX][currentY] == true ) return 0;                   // Wall

    visitedMap[currentX][currentY] = true;

    int numberofWays = 0;
    numberofWays += findNumberofWaysToMaze(maze, visitedMap, currentX-1, currentY, targetX, targetY );
    numberofWays += findNumberofWaysToMaze(maze, visitedMap, currentX+1, currentY, targetX, targetY );
    numberofWays += findNumberofWaysToMaze(maze, visitedMap, currentX, currentY-1, targetX, targetY );
    numberofWays += findNumberofWaysToMaze(maze, visitedMap, currentX, currentY+1, targetX, targetY );

    visitedMap[currentX][currentY] = false;
    return numberofWays;
}

You could of course make that private, and use the original one as a basic wrapper (to create and initialise visitedMap).