递归实现网格左上到右下路径：方向标记异常求助

问题描述 #

我尝试用递归实现从网格左上角到右下角的路径查找，规则是：每次只能按照当前格子的数字，向上下左右移动对应步数，且不能移出网格。找到路径后需要给格子标记移动方向（比如3L、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();
    }
}

预期输出说明 #

预期输出的网格中，路径上的每个格子会标记正确的移动方向（比如从左上角(0,0)出发的1会标记为1R，代表向右移动1步），右下角的终点格子保持原数字不变，同时输出正确的路径总长度。

问题排查与修复方案 #

核心问题1：方向与坐标移动完全不匹配 #

原代码中方向标记和实际坐标移动的对应逻辑完全错误：

• 标记R（右）却修改了x坐标（x+move），实际右移应该是y坐标增加
• 标记L（左）修改了x坐标（x-move），实际左移应该是y坐标减少
• 标记D（下）修改了y坐标（y-move），实际下移应该是x坐标增加
• 标记U（上）修改了y坐标（y+move），实际上下移应该是x坐标减少

正确的方向-坐标对应关系：

• R（右）：y += move，x不变
• L（左）：y -= move，x不变
• D（下）：x += move，y不变
• U（上）：x -= move，y不变

核心问题2：Grid对象未正确克隆 #

原代码调用了Clone()方法但未实现，导致所有递归分支共享同一个Grid实例，不同路径的标记会互相覆盖，最终输出混乱。需要实现深度克隆，每次递归传递新的Grid副本。

修复后的完整代码 #

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

    public Grid(int n) {
        this.n = n;
        this.grid = new String[n][n];
    }

    // 实现深度克隆，确保每个递归分支操作独立的网格实例
    public Grid Clone() {
        Grid cloned = new Grid(this.n);
        for (int i = 0; i < n; i++) {
            cloned.grid[i] = this.grid[i].clone();
        }
        return cloned;
    }

    public void findPath() {
        int[][] visited = new int[n][n];
        if (FindPathHelper(0, 0, visited, Clone(), 0)) {
            System.out.println("找到路径啦!!!");
        } else {
            System.out.println("未找到路径");
        }
    }

    public boolean FindPathHelper(int x, int y, int[][] visited, Grid box, int length) {
        int n = box.grid.length;
        // 到达终点，输出结果
        if (x == n - 1 && y == n - 1) {
            Display(box.grid);
            System.out.println("路径总长度: " + 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]);

        // 右移：y坐标增加move
        box.grid[x][y] = move + "R";
        if (FindPathHelper(x, y + move, visited, box.Clone(), length + move)) {
            return true;
        }

        // 左移：y坐标减少move
        box.grid[x][y] = move + "L";
        if (FindPathHelper(x, y - move, visited, box.Clone(), length + move)) {
            return true;
        }

        // 下移：x坐标增加move
        box.grid[x][y] = move + "D";
        if (FindPathHelper(x + move, y, visited, box.Clone(), length + move)) {
            return true;
        }

        // 上移：x坐标减少move
        box.grid[x][y] = move + "U";
        if (FindPathHelper(x - move, y, visited, box.Clone(), length + move)) {
            return true;
        }

        // 回溯：重置当前格子的访问标记
        visited[x][y] = 0;
        return false;
    }

    // 补充网格打印方法
    public void Display(String[][] grid) {
        for (String[] row : grid) {
            for (String cell : row) {
                System.out.print(cell + "\t");
            }
            System.out.println();
        }
    }
}

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

    public static void TestCases() {
        System.out.println("测试网格:");
        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();
    }
}

修复说明 #

1. 修正了方向标记与坐标移动的对应逻辑，确保每个标记的方向和实际移动一致
2. 实现了深度克隆的Clone()方法，每次递归传递独立的Grid实例，避免不同分支的标记互相干扰
3. 补充了缺失的构造方法和Display方法，保证代码可正常运行

内容的提问来源于stack exchange，提问作者HighHopes_0_0