2

这是作业中的一个问题，我被困住了，如果有人能指导我，我会很高兴。

通过在第一个单元格（第 0 行第 0 列）进行统计来定义合法路径，并通过将单元格中数字的第一位和第二位数字相加来计数到下一步，直到到达最后一个单元格（第 n 行第 n 列） ）。

例如：如果在单元格 [2][3] 中有数字 15，那么下一步可以是：行 +1 和列 +5 到 [3][8] 或行 +5 和 +1列到 [7][4]

该方法应该返回有多少合法路径。

我正在尝试对这个问题使用回溯递归方法，除了重载方法之外，我不能使用任何循环或任何其他方法。

这是我到目前为止提出的代码：

public static int countPaths (int[][] mat)
{
    return countPaths(mat,0,0);
}

private static int countPaths(int[][] mat, int col, int row)
{


    if ((col==mat.length-1 && row==mat[0].length-1 )  {
        return 1;
    }    
    return countPaths(mat,mat[col][row]/10+col,mat[col][row]%10+row) + countPaths(mat,mat[col][row]%10-col,mat[col][row]/10-row);

}

谢谢你的帮助 ！

4

5 回答 5

1

如果我正确理解了问题，这是一个解决方案。

公共类 MatrixPathCounter { 私有静态 int[][] mat = {{10,11,0},{10,11,10},{10,10,0}};

public static void main(String[] args)
{
    System.out.println(countPath(mat,0,0));
}

private static int countPath(int[][] mat, int x, int y)
{
    int n = mat.length -1;

    if (x==n && y==n)
        return 1;

    if(x>n || y>n)
        return 0;

    if(mat[x][y]==0)
        return 0;

    if(x+mat[x][y]/10 == x+mat[x][y]%10 && x+mat[x][y]%10 == x+mat[x][y]/10)
        return countPath(mat,x+mat[x][y]/10,y+mat[x][y]%10);
    else
        return countPath(mat,x+mat[x][y]/10,y+mat[x][y]%10) + countPath(mat,x+mat[x][y]%10,y+mat[x][y]/10 ); 
}

}

于 2013-05-24T17:43:26.177 回答
0

你快到了，有几件事：

  • 您计算可能尝试的后续步骤时似乎有错误
  • 您应该在访问数组/进行递归调用之前检查边界，以避免 ArrayOutOfBoundsException
于 2013-05-24T17:08:59.303 回答
0

因为这是一个家庭作业，所以只是我的一些提示

  1. 不仅返回 1 还返回失败状态。例如，如果列或行大于长度，则返回 0。（或者您可以使用 true/false）

  2. 您正在添加两个递归函数。而不是这样做尝试一个一个地做。例如，首先使用 (row+1,com+5) 检查是否返回失败，然后尝试 (row+5,col+1)。

于 2013-05-24T16:44:12.347 回答
0 
    return countPaths(mat,mat[col][row]/10+col,mat[col][row]%10+row) + countPaths(mat,mat[col][row]%10-col,mat[col][row]/10-row);

“通过在第一个单元格（第 0 行第 0 列）进行统计，定义了一条合法路径，并通过将单元格中数字的第一位和第二位数字相加来计数到下一步，直到到达最后一个单元格（第 n 行列） n)。

例如：如果在单元格 [2][3] 中有数字 15，那么下一步可以是：行 +1 和列 +5 到 [3][8] 或行 +5 和 +1列到 [7][4]"

在我看来，您在确定 row 和 col 时的逻辑在某种程度上有所偏差。无论如何，您应该得到相同的两位数，只需将它们调换即可。我的建议是将您的数字值存储在变量中，以使您的代码更清晰。我知道如何解决问题，但如果我为您解决问题，您将学不到任何东西。

正如另一位用户指出的那样，我还将确保通过检查它们是否仍然有效来关闭“死胡同”路径。此时，返回 0。

于 2013-05-24T16:49:18.777 回答
-1

这是我想出的：

public static void main(String[] args)
{
    int[][] mat = 
        {
                {12, 22, 23, 54},
                {43, 35, 21, 20},
                {34, 21, 43, 21},
                {25, 30, 0,  20},
                {0,  22, 10, 10},
                {20, 13, 3,  45},
        };
    
    System.out.println(countPaths(mat)); // 3
}

public static int countPaths(int[][] mat)
{
    return countPaths(mat, 0, 0);
}

private static int countPaths(int[][] mat, int row, int col)
{           
    if (row == mat.length - 1 && col == mat[row].length - 1)
        return 1;
    
    if (row >= mat.length || col >= mat[row].length)
        return 0;
    
    if (mat[row][col] <= 0 || mat[row][col] >= 100)
        return 0;
    
    int currentNumber = mat[row][col];
    int rightDigit = currentNumber % 10, leftDigit = (currentNumber / 10) % 10;
    
    int r1 = countPaths(mat, row + rightDigit, col + leftDigit);
    int r2 = countPaths(mat, row + leftDigit, col + rightDigit);
    
    return r1 + r2;
}
于 2021-06-04T14:32:24.443 回答