そのため、特定の迷路に最初から最後までいくつの方法が存在するかを見つけようとしています。
これが私のコードで、深さ優先検索を使用しています。
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 配列を使用しているためです。ただし、ソリューションを変更する方法がわかりません。コメントや提案は大歓迎です。
ありがとう