java - 递归头痛

Question

任务:

给定一个包含非负整数的二维数组m，我们将“路径”定义为相邻单元格的集合(对角线步骤不算作邻居) 从row == 0 && col == 0 开始到row == m.length - 1 && col == m[0].length - 1.

“路径”的成本是“路径”每个单元格中值的总和。

示例:

数组中的两个可能路径:

路径1(虚线)的成本:8 + 4 + 2 + 8 + 9 + 9 + 7 + 5 = 52；

路径 2(全线)的成本:8 + 6 + 3 + 8 + 9 + 4 + 1 + 2 + 1 + 7 + 6 + 5 = 60

待办事项:

编写一个static 递归方法，它接受一个二维数组m，其中填充了完整的非负值，并打印所有可能路径的总和成本(您可以假设 m 既不是 null 也不是空的)。

方法签名是(允许重载):

public static void printPathWeights(int [][] m)

我的代码:

public class Main {

    public static void main(String[] args) {

        int arr[][] = { { 1, 1, 1 },
                        { 1, 1, 1 },
                        { 1, 1, 1 }
        };

        printPathWeights(arr);

    }

    public static void printPathWeights(int[][] m) {
        System.out.println(printPathWeights(m, 0, 0, new int[m.length][m[0].length], 0));
    }


    /*
     * @param map marks the visited cells
     */
    private static int printPathWeights(int[][] m, int row, int col, int[][] map, int carrier) {

        if (row < 0 || col < 0 || row >= m.length || col >= m[0].length || map[row][col] == 1)
            return 0;

        if (row == m.length - 1 && col == m[0].length - 1)
            return m[row][col] + carrier;

        map[row][col] = 1;
        return printPathWeights(m, row + 1, col, map, carrier + m[row][col]) +
                printPathWeights(m, row - 1, col, map, carrier + m[row][col]) +
                printPathWeights(m, row, col + 1, map, carrier + m[row][col]) +
                printPathWeights(m, row, col - 1, map, carrier + m[row][col]);

    }

}

以上代码的打印值为:14

低于预期!

运行时:

    int arr[][] = { { 1, 1 },
                    { 1, 1 }
    };

结果是预期的 6。

我的代码有什么问题？

PS:请不要向我提供解决作业的代码，但请解释我的代码有什么问题。

Answer 1

只要任意路径到达该单元格，该代码就会标记已访问的单元格。但是此单元格随后也被标记为所有其他单元格已访问，并且不会再次访问。这意味着该算法仅完成路径的一个子集，并且对于更大的数组，一些遍历会在数组中间的某个地方中断。您必须为每条路径分别将单元格标记为已访问。

每次访问新单元格后简单地重置 map :

    printPathWeights(...)
        //analyze the current cell
        markCellVisited(currentCell)

        int tmp = visitAllNeighbours()

        resetVisitedState(currentCell)

        return tmp

这将是最有效和最简单的方法。由于 cellstate 在访问 cell 后被重置，因此它永远不会保留之前路径的标记。