2

我需要使用递归找到从1amatrix[R][C]开始matrix[0][0]直到它到达的数字的路径。matrix[R-1][C-1]我只能向下或向右。在大多数情况下，我没有问题。我的问题只有在无处可去的时候，我需要后退一步。

例如，这是我从文件中获取的矩阵：

1 0 0 0 0 0
1 1 0 0 0 0
1 1 0 0 0 0
1 1 1 1 0 1
1 0 1 1 1 1
0 1 0 1 1 1

问题是当它到达时matrix[4][0]。我不明白为什么它不会在递归中返回。当它应该返回 true 时，它​​返回 false。

这是代码：

int findPath(int matrix[][C],int rowSize,int colSize)
{
    int a=0,b=0;
    if(Find_Path(matrix,rowSize,colSize,a,b)==0)
    {
        printf("The function return - False\n");
        return 0;
    }
    else 
    {
        printf("The function return - True\n");
        return 1;
    }
} 

int Find_Path(int matrix[][C],int rowSize,int colSize,int a,int b)
{
    if(a==(rowSize-1) && (b==colSize-1))
        return 1;
    if(matrix[a+1][b]==1)
        return Find_Path(matrix,rowSize-1,colSize-1,a+1,b);
    if(matrix[a][b+1]==1)
        return Find_Path(matrix,rowSize-1,colSize-1,a,b+1);

    if(matrix[a+1][b]==0 && matrix[a][b+1]==0)
        return 0;
}
4

3 回答 3

3
  • 您的递归函数是错误的，因为它只尝试它看到的第一个“1”相邻单元格。
  • 递归错误地只查看矩阵的较小部分。您必须调整矩阵大小（但也要调整其原点）或坐标。不是都。
  • 失败条件（最后一个 if）是错误且虚假的。
    int Find_Path(int matrix[][C],int rowSize,int colSize,int a,int b)
    {
       if(a==(rowSize-1) && (b==colSize-1))
          返回 1；
       if(matrix[a+1][b]==1 && Find_Path(matrix,rowSize,colSize,a+1,b))
          返回 1；
       if(matrix[a][b+1]==1 && Find_Path(matrix,rowSize,colSize,a,b+1))
          返回 1；
       返回0；
    }

（虽然我还没有测试过。）

于 2013-01-25T16:55:44.743 回答
1

你需要检查你没有放弃矩阵，我发现在移动之后而不是在移动之前检查矩阵中的 1 和 0 稍微整洁一些。把它们放在一起给出了这个代码。

int find_path(int matrix[R][C], int i, int j) {
    if (!matrix[i][j]) return 0;
    if (i == R-1 && j == C-1) return 1;
    return i+1<R && find_path(matrix, i+1, j) ||
           j+1<C && find_path(matrix, i, j+1));
}
于 2013-01-25T17:50:46.347 回答
0

在[3][0],if(matrix[a+1][b]==1)会成功，它会尝试调用return Find_Path(matrix,rowSize-1,colSize-1,4,0);现在返回值为 0，那么你就直接返回了。1仅当该递归调用返回时才从该位置返回1。

if(matrix[a+1][b]==1)
    if(Find_Path(matrix,rowSize-1,colSize-1,a+1,b)) return 1;
if(matrix[a][b+1]==1)
    if(Find_Path(matrix,rowSize-1,colSize-1,a,b+1)) return 1;

因为在您的代码中调用了[4][0]它的返回0，并且您从那个地方返回本身带有0. 你不打算进行下一次检查if(matrix[a][b+1]==1)

于 2013-01-25T17:23:13.933 回答