+ 109

Challenge: Find The Longest Path In Matrix

Find the longest path in a matrix with given constraints 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 long

14th Sep 2017, 5:20 PM
GAWEN STEASY
GAWEN STEASY - avatar
69 ответов
+ 42
I used recursion function followPath(num,pathLength,pathnum,val){ if (num <= smallArr.length){ pathLength[pathnum]=val; if(isPath(num)){ followPath(num+1,pathLength,pathnum,val+1); } else{ followPath(num+1,pathLength,num,0); } } return pathLength; } https://code.sololearn.com/W3HgARPHhPjT/#html
17th Sep 2017, 6:24 PM
Louis
Louis - avatar
18th Sep 2017, 3:30 PM
Suresh
+ 15
Here's my C# implementation ✌ I thought this question requires recursion in the first place but found out it's not necessary after I begin to code. Any ideas to improve/simplify my code are welcome! P/S: The core algorithm is just the last 3 functions only. Short and sweet! ❤😁 https://code.sololearn.com/ca1XX2NMDa6R/?ref=app
15th Sep 2017, 9:26 AM
Zephyr Koo
Zephyr Koo - avatar
+ 10
@Dirac you can try to post the code 😊
18th Sep 2017, 5:03 PM
GAWEN STEASY
GAWEN STEASY - avatar
+ 8
we can use single source shortest path algorithm
19th Sep 2017, 5:10 AM
Geeta P Jerkal
Geeta P Jerkal - avatar
+ 8
sayan tq..
21st Sep 2017, 3:44 AM
Geeta P Jerkal
Geeta P Jerkal - avatar
+ 7
yeah @Sayan
14th Sep 2017, 6:31 PM
GAWEN STEASY
GAWEN STEASY - avatar
+ 7
here, one more of my not easy solutions 😁 https://code.sololearn.com/WKoZGtmITMPL/?ref=app
14th Sep 2017, 11:20 PM
ysraelcon
ysraelcon - avatar
+ 7
Hi, Here's another Python implementation: https://code.sololearn.com/c9Ul9MwiH85p/#py
16th Sep 2017, 5:46 AM
László Ozsvárt
László Ozsvárt - avatar
+ 7
@Sivan you can use any method to solve this just post your idea in a implementation😊
18th Sep 2017, 5:02 PM
GAWEN STEASY
GAWEN STEASY - avatar
+ 7
@Louis nice js coding style
18th Sep 2017, 5:27 PM
Abdur-Rahmaan Janhangeer
Abdur-Rahmaan Janhangeer - avatar
+ 7
Gaston which is a source and destination in matrix
21st Sep 2017, 3:10 AM
Geeta P Jerkal
Geeta P Jerkal - avatar
+ 7
to find longest path which is a source vertex
21st Sep 2017, 3:16 AM
Geeta P Jerkal
Geeta P Jerkal - avatar
+ 6
The longest path is 6-7-8-9. in this matrix
14th Sep 2017, 6:27 PM
GAWEN STEASY
GAWEN STEASY - avatar
+ 6
Great fun. Lots of constraints make this problem more variable for smaller n. ### Python Version: https://code.sololearn.com/cDB6Cpg8QI6K/#py # The key is recognizing that for each position in the matrix [i,j] there is only one unique path that satisfies the constraints. The minimum path is 1 ([i,j] has no adjacent neighbors that satisfy the rules) and the maximum possible path is n^2. # Additionally, when checking the 4 adjacent positions for validity, once one has been found that satisfies the difference-of-one condition, you do not need to check any other paths. This is because of the "distinct" rule of the generated matrix. I originally coded my result in R. But it won't run on SoloLearn. Here's the code anyway. ### R Version: https://code.sololearn.com/c8SbFy3OV14x
19th Sep 2017, 4:41 AM
Stacy Irwin
Stacy Irwin - avatar
+ 5
#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; }
18th Sep 2017, 5:32 PM
Jainam vora
Jainam vora - avatar
18th Sep 2017, 7:10 PM
ramakrishna
ramakrishna - avatar
+ 5
@koushik y Yup you may head to Discuss section and find the keyword "challenge". There are a lot of interesting challenges over there but this one stand out for this week and congrats to Gawen! 😁
19th Sep 2017, 2:22 PM
Zephyr Koo
Zephyr Koo - avatar