Find the longest path in a matrix with given constraints

link 0

Given a n*n matrix where all numbers are distinct, find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1.

We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1) with the condition that the adjacent cells have a difference of 1.

Example:

Input:  mat[][] = {{1, 2, 9}
                   {5, 3, 8}
                   {4, 6, 7}}
Output: 4
The longest path is 6-7-8-9.

The idea is simple, we calculate longest path beginning with every cell. Once we have computed longest for all cells, we return maximum of all longest paths. One important observation in this approach is many overlapping subproblems. Therefore this problem can be optimally solved using Dynamic Programming.

Below is Dynamic Programming based implementation that uses a lookup table dp[][] to check if a problem is already solved 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, 2, 9},
                    {5, 3, 8},
                    {4, 6, 7}};
   cout << "Length of the longest path is "
        << finLongestOverAll(mat);
   return 0;
}

Output:

Length of the longest path is 4

Time complexity of the above solution is O(n2). It may seem more at first look. If we take a closer look, we can notice that all values of dp[i][j] are computed only once.

 

Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar