Approach
We will solve this problem using backtracking and explore all the possible paths from the source to the destination cell. We will apply a depth-first search to explore all the possible paths:
-
To apply DFS Algorithm, explore all the possible 4 directions from the source cell and find the longest path from each adjacent cell. Mark the cell as visited for the current path on traversing a cell.
- After exploring all 4 directions, find the direction with the longest path and add 1 to that path (i.e., add the current cell to that path) to get the longest path from the current cell.
- After exploring all 4 directions, mark the current node as unvisited(backtrack).
Code in C++
#include<iostream>
#include<vector>
using namespace std;
int findLongestPath(
int n,int m,
vector<vector<bool> >& visited,
int sourceRow,int sourceColumn,
int destinationRow,int destinationColumn){
if(sourceRow<0 || sourceColumn<0 || sourceRow>=n || sourceColumn>=m){
return 0;
}
if(sourceRow==destinationRow && sourceColumn==destinationColumn){
// since we are already at the destination, therefore longest path is of 1 size only
return 1;
}
// Check if the current cell is already visited in the current path
if(visited[sourceRow][sourceColumn]==true){
return 0;
}
// mark the current cell visited for the further path
visited[sourceRow][sourceColumn] = true;
int longestPath = 1 + findLongestPath(n,m,visited,sourceRow+1,sourceColumn,destinationRow,destinationColumn);
longestPath = max(longestPath,1 + findLongestPath(n,m,visited,sourceRow-1,sourceColumn,destinationRow,destinationColumn));
longestPath = max(longestPath,1 + findLongestPath(n,m,visited,sourceRow,sourceColumn+1,destinationRow,destinationColumn));
longestPath = max(longestPath,1 + findLongestPath(n,m,visited,sourceRow,sourceColumn-1,destinationRow,destinationColumn));
// mark the current node as unvisited, so that it can be visited in some other path too
visited[sourceRow][sourceColumn] = false;
return longestPath;
}
int solve(vector<vector<int> >& matrix,vector<int> sourceCell,vector<int> destinationCell){
int n = matrix.size();
int m = matrix[0].size();
// visited will help in maintaining the already visited nodes in the current path
vector<vector<bool> > visited(n,vector<bool>(m,false));
return findLongestPath(n,m,visited,sourceCell[0],sourceCell[1],destinationCell[0],destinationCell[1]);
}
int main(){
vector<vector<int> > matrix{
{5,4,1,0},
{6,3,2,0},
{7,8,9,0}
};
vector<int> sourceCell{0,1}, destinationCell{2,2};
cout<<"Longest path from the source {0,1} to destination {2,2} is "<<solve(matrix,sourceCell,destinationCell)<<endl;
sourceCell = {1,1};
cout<<"Longest path from the source {1,1} to destination {2,2} is "<<solve(matrix,sourceCell,destinationCell)<<endl;
}

You can also try this code with Online C++ Compiler
Run Code
Output
Longest path from the source {0,1} to destination {2,2} is 12
Longest path from the source {1,1} to destination {2,2} is 11
Time Complexity
Since we will have 4 neighbors to explore for every cell, the time complexity is O(4(N*M)), where N = number of rows and M = number of columns in the matrix.
Space Complexity
Since we are maintaining a visited matrix to check the already visited nodes in the current path, space complexity is O(N*M), where N = number of rows and M = number of columns in the matrix.
Frequently Asked Questions
-
What is the difference between a tree and a graph?
Trees and graphs are different since there can never be loops in a tree, but we can have loops in a graph. Also, all the nodes in a tree are always connected, but that is not true for a graph.
-
What is the difference between a DFS Traversal and a BFS Traversal?
In a DFS traversal of a graph, we begin from any random node and travel down each branch as feasible before returning to the current node. In contrast, in a BFS traversal, we visit each node at the current level before visiting their children nodes.
DFS Traversal is performed using a stack, whereas a BFS Traversal is performed using a queue.
-
Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?
Yes, Coding Ninjas Studio offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.
Key Takeaways
This article taught us how to effectively use backtracking to determine the longest path from the source cell to the destination cell in a 2D matrix.
Since graphs are frequently asked in interviews, we recommend you practice more problems based on graphs on Coding Ninjas Studio.
Recommended Problems:
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!