c++recursionmatrixlongest-path

My c++ program has stopped working


I tried to find the longest path in a matrix with consecutive digits which gives correct answer.The function call executes recursively till there is no consecutive digits nearby and it checks every time whether the cell is visited or not

#include<bits/stdc++.h>
#define n 3
using namespace std;

// Returns length of the longest path beginning with mat[i][j].
// This function mainly uses lookup table dp[n][n]
int findLongestFromACell(int i, int j, int mat[n][n], int dp[n][n])
{
    // Base case
    if (i<0 || i>=n || j<0 || j>=n)
        return 0;

    // If this subproblem is already solved
    if (dp[i][j] != -1)
        return dp[i][j];

    // Since all numbers are unique and in range from 1 to n*n,
    // there is atmost one possible direction from any cell
    if (j<n-1 && ((mat[i][j] +1) == mat[i][j+1]))
       return dp[i][j] = 1 + findLongestFromACell(i,j+1,mat,dp);

    if (j>0 && (mat[i][j] +1 == mat[i][j-1]))
       return dp[i][j] = 1 + findLongestFromACell(i,j-1,mat,dp);

    if (i>0 && (mat[i][j] +1 == mat[i-1][j]))
       return dp[i][j] = 1 + findLongestFromACell(i-1,j,mat,dp);

    if (i<n-1 && (mat[i][j] +1 == mat[i+1][j]))
       return dp[i][j] = 1 + findLongestFromACell(i+1,j,mat,dp);

    // If none of the adjacent fours is one greater
    return dp[i][j] = 1;
}

// Returns length of the longest path beginning with any cell
int finLongestOverAll(int mat[n][n])
{
    int result = 1;  // Initialize result

    // Create a lookup table and fill all entries in it as -1
    int dp[n][n];
    memset(dp, -1, sizeof dp);

    // Compute longest path beginning from all cells
    for (int i=0; i<n; i++)
    {
      for (int j=0; j<n; j++)
       {
          if (dp[i][j] == -1)
             findLongestFromACell(i, j, mat, dp);

          //  Update result if needed
          result = max(result, dp[i][j]);
       }
     }

     return result;
}

// Driver program
int main()
{
   int  mat[n][n] = {{1, 10, 9},
                    {5, 3, 8},
                    {4, 6, 7}};
   cout << "Length of the longest path is "
        << finLongestOverAll(mat);
   return 0;
}

But when i tried the same code to find the longest path in a binary matrix the program stops executing

#include<bits/stdc++.h>
#define n 3
using namespace std;

// Returns length of the longest path beginning with mat[i][j].
// This function mainly uses lookup table dp[n][n]
int findLongestFromACell(int i, int j, int mat[n][n], int dp[n][n])
{
    // Base case
    if (i<0 || i>=n || j<0 || j>=n)
        return 0;

    // If this subproblem is already solved
    if (dp[i][j] != -1)
        return dp[i][j];

    // Since all numbers are unique and in range from 1 to n*n,
    // there is atmost one possible direction from any cell
    if (j<n-1 && (1 == mat[i][j+1]))
       return dp[i][j] = 1 + findLongestFromACell(i,j+1,mat,dp);

    if (j>0 && (1 == mat[i][j-1]))
       return dp[i][j] = 1 + findLongestFromACell(i,j-1,mat,dp);

    if (i>0 && (1 == mat[i-1][j]))
       return dp[i][j] = 1 + findLongestFromACell(i-1,j,mat,dp);

    if (i<n-1 && (1 == mat[i+1][j]))
       return dp[i][j] = 1 + findLongestFromACell(i+1,j,mat,dp);

    // If none of the adjacent fours is one greater
    return dp[i][j] = 1;
}

// Returns length of the longest path beginning with any cell
int finLongestOverAll(int mat[n][n])
{
    int result = 1;  // Initialize result

    // Create a lookup table and fill all entries in it as -1
    int dp[n][n];
    memset(dp, -1, sizeof dp);

    // Compute longest path beginning from all cells
    for (int i=0; i<n; i++)
    {
      for (int j=0; j<n; j++)
       {
          if (dp[i][j] == -1)
             findLongestFromACell(i, j, mat, dp);

          //  Update result if needed
          result = max(result, dp[i][j]);
       }
     }

     return result;
}

// Driver program
int main()
{
   int  mat[n][n] = {{1, 0, 0},
                    {1, 0, 0},
                    {1, 1, 1}};
   cout << "Length of the longest path is "
        << finLongestOverAll(mat);
   return 0;
}

what is the error in this code.Thanks in advance


Solution

  • Your algorithm has a problem. You rely on the fact that

    there is atmost one possible direction from any cell

    and that that path can never be circular.

    In case of a binary matrix that conditions are bound to fail. You move from (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) to (0,0) to (1,0) an so on :-)

    So your algorithm terminates when the stack is full since with the preconditions you chose the longest path length is infinite and only Chuck Norris can do infinite loops in finite time.

    Edit: I strongly support the comment by Xeverous. You really should refactor your code to be more c++. That makes the code easier to read and you would have easily seen the problem.