查找所有路径问题（Java中的递归和回溯）

Question

我一直在关注 Java 数据结构和算法的播放列表，并且遇到了回溯主题，其中给你一个木板以及起点 (0,0) 和终点 (board_length,board_width)。任务是查找并打印以您不访问的方式发生的所有可能路径，并将先前访问过的路径平铺在正在进行递归调用的当前路径中。

这是该问题的java代码：

import java.util.ArrayList;
import java.util.Arrays;

public class Main {

    public static void main(String[] args){
        boolean[][] board={{false,false,false},
                           {false,false,false},
                           {false,false,false},
    };
        ArrayList<String> ans=countPath("",0,0,board);
        System.out.println(ans);
    }

    static ArrayList<String> countPath(String path,int r,int c,boolean[][] board){
        ArrayList<String> ans=new ArrayList<>();
        if(r==board.length-1 && c==board[0].length-1){
            ans.add(path);
            return ans;
        }else if(board[r][c]){
            board[r][c]=false;
            path=path.substring(0,path.length()-1);
            return ans;
        }else{
            ArrayList<String> temp=new ArrayList<>();
            board[r][c]=true;
            if(r>0){
                temp=countPath(path+"U",r-1,c,board);
                ans.addAll(temp);
            }

            if(c<2){
                temp=countPath(path+"R",r,c+1,board);
                ans.addAll(temp);
            }

            if(r<2){
                temp=countPath(path+"D",r+1,c,board);
                ans.addAll(temp);

            }

            if(c>0){
                temp=countPath(path+"L",r,c-1,board);
                ans.addAll(temp);
            }
            board[r][c]=false;
            path=path.substring(0,path.length()-1);
            return ans;
        }
    }
}

但是我收到堆栈溢出错误，我不知道如何修复，因为我不知道为什么它会抛出堆栈溢出错误。我确实知道这与引发错误的某些循环有关，但我无法弄清楚它是哪个循环。请帮我指出那个循环

以下是我遇到的错误

Exception in thread "main" java.lang.StackOverflowError
    at Main.countPath(Main.java:23)
    at Main.countPath(Main.java:29)
    at Main.countPath(Main.java:39)
        ... and so on as it is recursion

我尝试调试代码文件并观察到路径变量发生循环，但我无法弄清楚如何阻止该循环发生。我已经提供了不返回到之前访问过的图块的限制，但它仍然抛出错误

Answer 1

首先，首先自动格式化代码，以便运算符之间有空格。否则很难阅读。

---

看看你的

else

分支：

if (r == board.length - 1 && c == board[0].length - 1) {
    // a solution was found; record it
}
else if (board[r][c]) {
    // cell hasn't been visited; mark it as visited and return the answer
else {
    // cell was already visited; mark it as unvisited and keep searching
}

这显然是错误的。如果您取消标记已访问过的内容并继续处理它，您将陷入无限循环并最终耗尽堆栈内存。

正确的逻辑是：

if (r == board.length - 1 && c == board[0].length - 1) {
    // a solution was found; record it
}
else if (board[r][c]) {
    // cell hasn't been visited; mark it as visited and keep searching
}
else {
    // cell was already visited; do nothing
}

换句话说，将所有递归逻辑移至

else if

。

此外，

ans

需要是参数或类变量（最好是前者），以便它在调用之间保持不变。如果您在每次调用时都重新创建它，那么当您返回它时它几乎是空的。结果数组列表应该只有一个。