之后结束
。
我正在尝试找到端位的路径。这是一个递归函数。请帮忙，我要自杀。
这是给定的地图
{ 1, 1, 1, 1 },
{ 0, 0, 1, 0 },
{ 0, 0, 1, 0 },
{ 0, 0, 1, 0 }};
我想递归地使用getPath以进入上面地图中的端位。参数是电流位置，端位和地图。在此示例中，起始位置是（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);
您实际上确实需要在所有
return Path创建一个函数，该函数以参数为开始和结束位置。它可以扫描通风道路的每条路径。因此，如果您可以向北，西，南，东部扫描这些位置的" 1"。如果找到1，请再次将函数调用，以将" 1"作为新的起始位置。通过到目前为止的路径和目标端位置。一旦其中一个找到了在给定端位置的" 1"匹配，您就已经到达了路径。这可能不是最佳路径。如果需要，请解析所有可能的路径，然后选择最短。最终，您的路后退以获取所有要点。由于该函数随着到目前为止的参数访问而获得的，因此请确保您不会通过排除未来路径的那些。
public static List<Point> getPath(Point start, Point end, int[][] Map)
{
//Current Position for the currentPosition
// EndPosition, given any point in the map would be the end of the maze
// map is that map that given for example or any other map
// returns an arraylist of positions of the paths
ArrayList<Point> result = new ArrayList<Point>();
boolean solutionExists = buildSolution(start, end, Map, result, new HashSet<Point>());
return solutionExists? result : null;
}
public static boolean buildSolution(Point current, Point end, int[][] map, List<Point> solution, Set<Point> visited) {
visited.add(current);
if (current.equals(end)) {
solution.add(current);
return true;
}
if (map[current.x][current.y] == 0) {
return false;
}
Set<Point> neighbours = getNeighbours(current, map);
neighbours.removeAll(visited);
for (Point neighbour : neighbours) {
ArrayList<Point> temp = new ArrayList<Point>();
Set<Point> tempVisited = new HashSet<Point>(visited);
tempVisited.add(neighbour);
if (buildSolution(neighbour, end, map, temp, tempVisited)) {
solution.add(current);
solution.addAll(temp);
return true;
}
}
return false;
}
public static Set<Point> getNeighbours(Point current, int[][] map) {
int maxX = map.length - 1;
int maxY = map[0].length - 1;
Set<Point> result = new HashSet<Point>();
result.add(new Point(current.x, current.y - 1 < 0 ? current.y :current.y -1));
result.add(new Point(current.x, current.y + 1 > maxY ? current.y : current.y +1));
result.add(new Point(current.x - 1 < 0 ? current.x : current.x -1 , current.y));
result.add(new Point(current.x + 1 > maxX ? current.x : current.x + 1, current.y));
result.remove(current);
return result;
}