CODEWITHSUNDEEP
crecursionmatrixtail-recursion
nivo123
nivo123

Reputation: 65

Recursive path finding in matrix

I need to find a path of the number 1 in a matrix[R][C] starting from matrix[0][0] until it gets to matrix[R-1][C-1], using recursion. I can only go down or right. In most cases, I don't have a problem. My problem is only when there is nowhere to go, and I need to take a step backwards.

Per example, this is the matrix I'm getting from a file:

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

The problem is when it gets to matrix[4][0]. I don't understand why it won't go back in the recursion. It returns false when it should return true.

This is the code:

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;
}

Upvotes: 2

Views: 10319

Answers (3)

mity
mity

Reputation: 2349

  • Your recursion function is wrong in that it only tries first '1' neighbor cell it sees.
  • The recursion erroneously takes a look only to smaller part of the matrix. You have either to adapt the matrix size (but then also its origin), or coordinates. Not both.
  • The fail condition (the last if) is wrong and bogus.
    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;
    }

(I have not tested it though.)

Upvotes: 3

rashok
rashok

Reputation: 13414

At [3][0], if(matrix[a+1][b]==1) will get succeeded and it will try to call return Find_Path(matrix,rowSize-1,colSize-1,4,0); Now the return value is 0, then you are returning directly. Return 1 from that place only if that recursive call returns 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;

Becuase in your code call for [4][0] its returning 0 and you are returning from that place itself with 0. You are not going for the next check if(matrix[a][b+1]==1)

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58231

You need to check you're not dropping off the matrix, and I find it slightly neater to check the 1's and 0's in the matrix after rather than before the move. Putting those together gives this code.

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));
}

Upvotes: 1

Related Questions