3

所以我试图找出一个给定的迷宫从头到尾有多少种方式存在。

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

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 表示阻止）。我知道原因是因为我使用另一个二维数组来记录一个点是否被访问过。但是，我不知道如何修改我的解决方案。任何意见或建议将不胜感激。

谢谢

4

1 回答 1

2

你假设你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）。

于 2013-06-11T04:34:41.070 回答