java - 二维数组的递归

Question

我正在编写一个递归方法来查找二维数组中的所有可能路径。从左上角点(0,0)到右下点最后一个点。并返回路径的总和。

public static void printPathWeights(int[][] m)
{
    printPathWeights(m, 0, 0, 0);
}

public static void printPathWeights(int[][] m, int row, int col, int sum)
{
    if(row == 0 && col ==0)
    sum = 0;

    if (row == m.length - 1 && col == m[row].length - 1)
        System.out.println(sum);

    else
    {
        if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
        printPathWeights(m, row - 1, col, sum += m[row][col]); // Up
        if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
            printPathWeights(m, row + 1, col, sum += m[row][col]); // Down
        if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
            printPathWeights(m, row, col - 1, sum += m[row][col]); // Left
        if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
            printPathWeights(m, row, col + 1, sum += m[row][col]); // Right
    }
}

目前我的问题是这个函数进入无限循环并且不打印我的总和

Answer 1

我认为它陷入了困境:

if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
        printPathWeights(m, row, col - 1, sum += m[row][col]); // Left
if (row >= 0 && row < m.length && col >= 0 && col < m[row].length)
        printPathWeights(m, row, col + 1, sum += m[row][col]); // Right

它将永远不断地来回跳跃。

而且，正如 Miquel 指出的那样，为什么路径不能向上延伸？

解决方案:(假设路径不能交叉，否则总和会趋于无穷大)

• 记录您去过的地方。将该历史记录传递到下一个递归。

• 将您所在图 block 的值添加到作为参数传递的总和值中。

• 如果您已到达终点，请打印总和。

• 其他:尝试朝四个可能的方向发展。如果该方向上没有单元格，则此操作将会失败，即您位于边缘。如果您已经去过那里，它也会失败。

• 如果你无法移动到任何地方，即你被卡住了，你就什么都不做就返回。