使用递归查找网格中从左上角到右下角的路径

Question

我正在尝试使用递归从网格的左上角移动到右下角。然而，在每个时间点，我只能向上、向下、向左或向右移动我所站立的数字给出的方格数量。

例如，如果你站在 3 上，我可以向左移动 3 个格子，向右移动 3 个格子，向上移动 3 个格子，或者向下移动 3 个格子。我无法离开黑板。如果找到路径，网格中会显示特定条目，指示所进行的移动，例如 3L（向左 3 个方格）或 3R（向右 # 个方格）。可变长度是总路径长度

这是我构建该方法的尝试。它返回一个长度，但网格中显示的条目没有给出合理的方向。有人可以帮忙吗？

public class Grid{
String [][] grid;
int n;

public void findPath()
    {


        int[][] visited = new int[n][n];

        if(FindPathHelper(0,0,visited, Clone(),0))
            System.out.println("Path was found!!!");
        else
            System.out.println("Path was not found");
    }


public boolean FindPathHelper(int x, int y, int[][] visited, Grid box, int length) {
        int n = box.grid.length; // Assuming n is the size of the grid
        if (x == n - 1 && y == n - 1) {
            box.Display(box.grid);
            System.out.println("Length is " + length);
            return true;
        }

        if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] == 1)
            return false;

        visited[x][y] = 1;

        int move = Integer.valueOf(grid[x][y]);


            box.grid[x][y] = move + "R";
            if (FindPathHelper(x + move, y, visited, box, length + move))
                return true;

            box.grid[x][y] = move + "L";
            if (FindPathHelper(x - move, y, visited, box, length + move))
                return true;

            box.grid[x][y] = move + "D";
            if (FindPathHelper(x, y - move, visited, box, length + move))
                return true;

            box.grid[x][y] = move + "U";
            if (FindPathHelper(x, y + move, visited, box, length + move))
                return true;


        box.grid[x][y] = grid[x][y];
        visited[x][y] = 0; // Reset the visited flag if no path was found
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
  TestCases();


    }

    public static void TestCases(){
        System.out.println("Test Grid :");
        Grid testG = new Grid(5);
        testG.grid = new String[][]{{"1","2","5","4","3"},{"2","3","1","3", "1"},{"3","3","2","1","1"},
                {"5","2","2","4","2"},{"5","2","1","1","1"}};
        testG.Display(testG.grid);
        System.out.println();
        testG.findPath();
    }

Answer 1

主要问题是您的算法不会比较路径的长度来检查它是否会返回具有“最短”路径的解决方案：它满足于找到的第一条路径，并立即退出搜索而不寻求改进。 因此，您必须继续前进，并跟踪找到的最短路径，而不是

return true;

中的那些

FindPathHelper

。为此，您需要一个额外的变量来代表迄今为止的最佳解决方案。例如，它可以是网格的克隆，或者是具有所采取的方向序列的字符串。DFS 的缺点是你必须尝试所有的可能性。如果您能实现“最佳搜索”算法，例如 Dijkstra 算法或 A* 算法，那就更好了。这些算法并行扩展多条路径，总是首先选择最有希望的路径。如果实施得好，找到的第一条路径也将是最短的。