我正在尝试找到到达 EndPosition 的路径。这是一个递归函数。请帮帮我,我快要自杀了。
这是给定的 map
{ 1, 1, 1, 1 },
{ 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 1, 0 }};
我想递归地使用 GetPath 来到达上面 map 中的 EndPosition。参数是当前位置、结束位置和 map 。对于此示例,起始位置为 (0,0),结束位置为 (0,3)(右上角)。 0 代表墙壁,1 代表路径。
我需要返回一个数组列表,其中填充了结束位置的有效点。尽管我的数组大小始终为 0 并且基本情况永远不会返回路径。如何跟踪数组列表中的位置?
请帮忙,不胜感激
private ArrayList<Point> GetPath(Point CurrentPosition, Point EndPosition, int[][] Map)
{
System.out.println("Current Position: " + CurrentPosition.toString());
ArrayList<Point> p = new ArrayList<Point>();
Path.add(CurrentPosition);
if (CurrentPosition.equals(EndPosition))
{
return Path;
}
Map[(int)CurrentPosition.getX()][(int) CurrentPosition.getY()] = 0; //setting to 0 so my function wont revisit that position in the map
ArrayList<Point> p2 = new ArrayList<Point>(); //Array for the 4 points around the CurrentPosition
p2.add(new Point((int) CurrentPosition.getX(), (int) CurrentPosition.getY()+1));
p2.add(new Point((int) CurrentPosition.getX()+1, (int) CurrentPosition.getY()));
p2.add(new Point((int) CurrentPosition.getX(), (int) CurrentPosition.getY()-1));
p2.add(new Point((int) CurrentPosition.getX()-1, (int) CurrentPosition.getY()));
for (int i = 0; i < p2.size(); i++)
{
int j = 0;
if (((p2.get(i).getX() >= 0 && p2.get(i).getY() >= 0) && (p2.get(i).getX() < Map.length && p2.get(i).getY() < Map[0].length)) && Map[(int) p2.get(i).getX()][(int) p2.get(i).getY()] !=0) //if the points in the array are within range and if the points aren't equal to 0.
{
Map[(int)p2.get(i).getX()][(int)p2.get(i).getY()] = 0;
GetPath(p2.get(i), EndPosition, Map); //recursive method
}
}
return Path;
}
最佳答案
我想我可能已经发现了问题:
您永远不会对递归调用的返回值执行任何操作:
...
Map[(int)p2.get(i).getX()][(int)p2.get(i).getY()] = 0;
GetPath(p2.get(i), EndPosition, Map); //recursive method
...
您应该执行以下操作:
ArrayList<Point> recPath = GetPath(p2.get(i), EndPosition, Map); //recursive method
Path.addAll(recPath);
您实际上确实需要在最后返回 Path
关于java - 用递归java解决迷宫问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22264183/