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 であり、明らかに、指定された迷路には 4 つの方法があります (false は合格を意味し、true はブロックを意味します)。その理由は、ポイントが訪問されたかどうかを記録するために別の 2D 配列を使用しているためです。ただし、ソリューションを変更する方法がわかりません。コメントや提案は大歓迎です。

ありがとう

4

1 に答える 1

2

あなたがvisitedMap問題を引き起こしていると仮定するのは正しいです。問題は、複数のパスが同じノードを通過できるということです。したがって、ターゲットにすぐ隣接する可能性のある位置は 2 つしかないため、結果は 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 に答える