java - 用递归 java 解决迷宫

Question

我试图找到 EndPosition 的路径。这是一个递归函数。请帮忙，我要自杀了。

这是给定的 map

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

我想递归地使用 GetPath 来到达上面 map 中的 EndPosition。参数是currentPosition、结束位置和 map 。对于此示例，起始位置为 (0,0) 并结束，EndPosition 为 (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;

Answer 1

我想我可能已经发现问题了:

您永远不会对递归调用的返回值做任何事情:

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