java - 给定迷宫中从开始到结束的路数

因此，我试图找出给定迷宫中从头到尾存在多少种方式。

这是我的代码，使用深度优先搜索。

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));
}

}

但是，输出不正确。我的输出是2，显然，给定迷宫中有四种方式(false表示可以通过，true表示通过)。我知道原因是因为我使用另一个2D数组来记录是否已访问一个点。但是，我不知道如何修改我的解决方案。任何意见或建议，将不胜感激。

谢谢

最佳答案

您以为visitedMap引起了问题是正确的。事实是，多个路径可以通过同一个节点，因此得到的结果为2，因为只有两个可能的位置紧邻目标。

不幸的是，您实现的堆栈无法将访问点的路径退回到添加每个位置时可用的位置。

这将使您更容易地递归实现。输入函数时，将(currentX, currentY)上的点标记为已访问。离开该功能时，将其取消标记。那将正确地解开您的道路。

您的功能将如下所示:

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;
}

您当然可以将其设为私有，并使用原始的作为基本包装(以创建和初始化visitedMap)。

关于java - 给定迷宫中从开始到结束的路数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17036318/