c - 矩阵中的递归路径查找

Question

我需要在从matrix[0][0]开始的matrix[R][C]中找到数字1的路径 code> 直到使用递归到达 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;
} 

Answer 1

• 您的递归函数是错误的，因为它只尝试第一个“1” 它看到邻居细胞。
• 递归错误地只查看矩阵的较小部分。您必须调整矩阵大小(但也要调整其原点)或坐标。两者都不是。
• 失败条件(最后一个 if)是错误的且是伪造的。

    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  &&  Find_Path(matrix,rowSize,colSize,a+1,b))
          return 1;
       if(matrix[a][b+1]==1  &&  Find_Path(matrix,rowSize,colSize,a,b+1))
          return 1;
       return 0;
    }

(不过我还没有测试过。)