递归-查找许多唯一路径-StackOverflowError

Question

我需要使用特殊的步进方法和递归从迷宫中找到从第一个到最后一个单元格的许多唯一路径。这适用于60步左右的水平。到JavaVisualizer，然后引发堆栈溢出错误。我不明白我错过了哪种异常情况，因为它的工作方式就像是进入数组的一半：（（

public class testerTable {

    // main method
    public static int countPaths(int[][] mat) {

        return moveColsRows(mat) + moveRowsCols(mat);
    }

    public static int countPaths(int[][] mat, int a, int b) {

        return moveColsRows(mat, a, b) + moveRowsCols(mat, a, b);
    }

    private static int moveRowsCols(int[][] arr) {
        //10 are rows, 00 are cols
        int newRows = (arr[0][0] / 10) % 10;
        int newCols = (arr[0][0]) % 10;
        //start checking the new cell - is new cell inside the table?
        if (newRows < arr.length && newCols < arr[0].length) {
            //is it the destination?
            if (newRows == arr.length && newCols == arr[0].length) {
                return 1;
            } else {
                // is it 0?
                if (arr[newRows][newCols] == 0) {
                    return 0;
                } else {
                    return countPaths(arr, newRows, newCols);
                }
                //run count Paths on it again
            }

        } else {
            //if cell is outside the limits of the table
            return 0;
        }
        //end of checking the new cell
    }

    private static int moveColsRows(int[][] arr) {
        //10 are cols, 00 are rows
        int newRows = (arr[0][0]) % 10;
        int newCols = (arr[0][0] / 10) % 10;
        //start checking the new cell - is new cell inside the table?
        if (newRows < arr.length && newCols < arr[0].length) {
            //is it the destination?
            if (newRows == arr.length && newCols == arr[0].length) {
                return 1;
            } else {
                // is it 0?
                if (arr[newRows][newCols] == 0) {
                    return 0;
                } else {
                    return countPaths(arr, newRows, newCols);
                }
                //run count Paths on it again
            }

        } else {
            //if cell is outside the limits of the table
            return 0;
        }
        //end of checking the new cell
    }

    //overriding move steps to start looking from a certain point in array
    private static int moveRowsCols(int[][] arr, int a, int b) {
        //10 are rows, 00 are cols
        int newRows = (arr[a][b] / 10) % 10;
        int newCols = (arr[a][b]) % 10;
        //start checking the new cell - is new cell inside the table?
        if (newRows < arr.length && newCols < arr[0].length) {
            //is it the destination?
            if (newRows == arr.length && newCols == arr[0].length) {
                return 1;
            } else {
                // is it 0?
                if (arr[newRows][newCols] == 0) {
                    return 0;
                } else {
                    return countPaths(arr, newRows, newCols);
                }
                //run count Paths on it again
            }

        } else {
            //if cell is outside the limits of the table
            return 0;
        }
        //end of checking the new cell
    }

    private static int moveColsRows(int[][] arr, int a, int b) {
        //10 are cols, 00 are rows
        int newRows = (arr[a][b]) % 10;
        int newCols = (arr[a][b] / 10) % 10;
        //start checking the new cell - is new cell inside the table?
        if (newRows < arr.length && newCols < arr[0].length) {
            //is it the destination?
            if (newRows == arr.length && newCols == arr[0].length) {
                return 1;
            } else {
                // is it 0?
                if (arr[newRows][newCols] == 0) {
                    return 0;
                } else {
                    return countPaths(arr, newRows, newCols);
                }
                //run count Paths on it again
            }

        } else {
            //if cell is outside the limits of the table
            return 0;
        }
        //end of checking the new cell
    }

}

Answer 1

[从代码中，我知道您有一个介于0到99之间的数字的网格（例如10x10，大小。您从（0，0）开始搜索，然后在该网格元素处选取数字XY，这意味着您可以转到（X，Y）和（Y，X）。从那里继续，直到达到（9，9）的目标。

我想，您遇到了堆栈溢出错误，因为您在迷宫中绕圈跑动。实际上，您具有某种圆形检测功能（当检查“ if（arr [newRows] [newCols] == 0“时），但这仅适用于返回第一个网格元素的圆形。当前，您实际上并没有真正检测到圆形迷宫。

首先，我建议稍微清理一下代码。有四种不同的穿越迷宫的方法容易出错。

然后您需要找到一种方法来防止圈子。我会给您一个提示：您需要以某种方式记住您去过的地方。与方法（递归或迭代）无关，如果您不记得自己去过的地方，您会发现自己正在圈子中奔跑。就像关于Ariadne（https://en.wikipedia.org/wiki/Ariadne）的故事一样。