用递归java求解迷宫

Question

我正在尝试寻找到EndPotion的路径。这是一个递归函数。请帮助，我要自杀了。

这是给定的地图

 { 1, 1, 1, 1 },
 { 0, 0, 1, 0 },
 { 0, 0, 1, 0 },
 { 0, 0, 1, 0 }};

我想递归地使用GetPath来到达上面地图中的EndPotion。参数是当前位置、结束位置和地图。对于这个例子，起始位置是（0,0）和结束，EndPotionis是（0,3），右上角。0代表墙壁，1代表路径。

我需要返回一个包含有效点的arraylist到结束位置。虽然我的数组大小始终为0，并且基本大小写永远不会返回路径。如何跟踪arraylist中的位置？

请帮忙，谢谢

  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;

}

Answer 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;
}

Answer 2

创建一个函数，将开始和结束位置作为参数。让它扫描每条路径以获得清晰的道路。因此，如果您可以向北、向西、向南、向东扫描这些位置以获取“1”。如果您找到1，请让函数再次调用自己，将找到“1”的点作为新的开始位置。传入到目前为止的路径和目标的结束位置。一旦其中一个在给定的结束位置找到“1”的匹配项，您就到达了您的路径。这可能不是最佳路径。如果您需要，解析所有可能的路径并选择最短的路径。最后向后遍历您的路径以获取所有点。由于该函数作为参数点访问到目前为止，确保您不会再次通过从未来路径中排除这些参数点来访问相同的点。

Answer 3

我想我可能发现了问题：

您从未对递归调用的返回值执行任何操作：

...
 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