2

再帰を使用して、から始まるまでの数字1のパスを見つける必要があります。下か右しか行けません。ほとんどの場合、問題はありません。私の問題は、行き場がなく、一歩後退する必要があるときだけです。matrix[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 に答える