Longest path in a Matrix from a specific source cell to destination cell
Given a matrix mat[][], and the coordinates of source and destination node, the task is to find the length of the longest path from source to destination.
Example:
Input: mat[][] = {{5, 6, 7, 8}, {4, 1, 0, 9}, {3, 2, 11, 10}}, src = {1, 1}, dest = {2, 2}
Output: 11
Explanation: The longest path between the coordinates (1, 1) and (2, 2) has 11 nodes and the path is given as 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11.Input: mat = {{5, 4, 1, 0}, {6, 3, 2, 0}, {7, 8, 9, 0}}, src = {0, 1}, dest = {2, 2}
Output: 12
Approach: The given problem can be solved using recursion and backtracking. The idea is to use depth-first-search to explore every path from source to destination and calculate the number of nodes between the path. Follow the steps below to solve the problem:
- Apply depth-first-search from source node to destination node
- Traverse in the four mentioned directions and at every node, increment the number of nodes traveled.
- Mark the nodes in the current path as visited in the visited[][] array and recursively call for the unvisited nodes in all four directions.
- After reaching the destination node update the maximum number of nodes required to be traveled to reach the destination.
- Maintain the maximum number of nodes over all paths which is the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Depth-First-Search function for // recursion and backtracking void dfs(vector<vector< int >> mat, int maxi[], vector<vector< int >> visited, int len, int i, int j, int dest[]) { // Return if current node is already // visited or it is out of bounds if (i < 0 || j < 0 || i == mat.size() || j == mat[0].size() || visited[i][j]) return ; // If reached the destination // then update maximum length if (i == dest[0] && j == dest[1]) { // Update max maxi[0] = max(maxi[0], len); return ; } // Mark current node as visited visited[i][j] = true ; // Recursive call in all // the four directions dfs(mat, maxi, visited, len + 1, i, j - 1, dest); dfs(mat, maxi, visited, len + 1, i + 1, j, dest); dfs(mat, maxi, visited, len + 1, i - 1, j, dest); dfs(mat, maxi, visited, len + 1, i, j + 1, dest); // Mark current cell as unvisited visited[i][j] = false ; } // Function to find the length of // the longest path between two nodes int longestPath(vector<vector< int >> mat, int src[], int dest[]) { // Initialize a variable to // calculate longest path int maxi[1]; maxi[0] = 0; // Number of rows int N = mat.size(); // Number of columns int M = mat[0].size(); // Initialize a boolean matrix to // keep track of the cells visited vector<vector< int >> visited(N, vector< int >(M, 0)); // Call the depth-first-search dfs(mat, maxi, visited, 0, src[0], src[1], dest); // Return the answer return maxi[0] + 1; } // Driver code int main() { vector<vector< int >> mat = {{5, 6, 7, 8}, {4, 1, 0, 9}, {3, 2, 11, 10}}; int src[] = {1, 1}; int dest[] = {2, 2}; cout << (longestPath(mat, src, dest)); } // This code is contributed by Potta Lokesh |
Java
// Java implementation for the above approach import java.io.*; import java.lang.Math; import java.util.*; // Driver code class GFG { // Function to find the length of // the longest path between two nodes public static int longestPath( int [][] mat, int [] src, int [] dest) { // Initialize a variable to // calculate longest path int [] max = new int [ 1 ]; // Number of rows int N = mat.length; // Number of columns int M = mat[ 0 ].length; // Initialize a boolean matrix to // keep track of the cells visited boolean [][] visited = new boolean [N][M]; // Call the depth-first-search dfs(mat, max, visited, 0 , src[ 0 ], src[ 1 ], dest); // Return the answer return max[ 0 ] + 1 ; } // Depth-First-Search function for // recursion and backtracking public static void dfs( int [][] mat, int [] max, boolean [][] visited, int len, int i, int j, int [] dest) { // Return if current node is already // visited or it is out of bounds if (i < 0 || j < 0 || i == mat.length || j == mat[ 0 ].length || visited[i][j]) return ; // If reached the destination // then update maximum length if (i == dest[ 0 ] && j == dest[ 1 ]) { // Update max max[ 0 ] = Math.max(max[ 0 ], len); return ; } // Mark current node as visited visited[i][j] = true ; // Recursive call in all // the four directions dfs(mat, max, visited, len + 1 , i, j - 1 , dest); dfs(mat, max, visited, len + 1 , i + 1 , j, dest); dfs(mat, max, visited, len + 1 , i - 1 , j, dest); dfs(mat, max, visited, len + 1 , i, j + 1 , dest); // Mark current cell as unvisited visited[i][j] = false ; } // Driver code public static void main(String[] args) { int [][] mat = { { 5 , 6 , 7 , 8 }, { 4 , 1 , 0 , 9 }, { 3 , 2 , 11 , 10 } }; int [] src = { 1 , 1 }; int [] dest = { 2 , 2 }; System.out.println(longestPath(mat, src, dest)); } } |
Python3
# Python 3 implementation for the above approach # Depth-First-Search function for # recursion and backtracking def dfs(mat, maxi, visited, length, i, j, dest): # Return if current node is already # visited or it is out of bounds if (i < 0 or j < 0 or i = = len (mat) or j = = len (mat[ 0 ]) or visited[i][j]): return # If reached the destination # then update maximum length if (i = = dest[ 0 ] and j = = dest[ 1 ]): # Update max maxi[ 0 ] = max (maxi[ 0 ], length) return # Mark current node as visited visited[i][j] = True # Recursive call in all # the four directions dfs(mat, maxi, visited, length + 1 , i, j - 1 , dest) dfs(mat, maxi, visited, length + 1 , i + 1 , j, dest) dfs(mat, maxi, visited, length + 1 , i - 1 , j, dest) dfs(mat, maxi, visited, length + 1 , i, j + 1 , dest) # Mark current cell as unvisited visited[i][j] = False # Function to find the length of # the longest path between two nodes def longestPath(mat, src, dest): # Initialize a variable to # calculate longest path maxi = [ 0 ] * 1 maxi[ 0 ] = 0 # Number of rows N = len (mat) # Number of columns M = len (mat[ 0 ]) # Initialize a boolean matrix to # keep track of the cells visited visited = [[ 0 for x in range (M)] for y in range (N)] # Call the depth-first-search dfs(mat, maxi, visited, 0 , src[ 0 ], src[ 1 ], dest) # Return the answer return maxi[ 0 ] + 1 # Driver code if __name__ = = "__main__" : mat = [[ 5 , 6 , 7 , 8 ], [ 4 , 1 , 0 , 9 ], [ 3 , 2 , 11 , 10 ]] src = [ 1 , 1 ] dest = [ 2 , 2 ] print (longestPath(mat, src, dest)) # This code is contributed by ukasp. |
C#
// C# implementation for the above approach using System; // Driver code class GFG { // Function to find the length of // the longest path between two nodes public static int longestPath( int [,] mat, int [] src, int [] dest) { // Initialize a variable to // calculate longest path int [] max = new int [1]; // Number of rows int N = mat.GetLength(0); // Number of columns int M = mat.GetLength(1); // Initialize a boolean matrix to // keep track of the cells visited bool [,] visited = new bool [N, M]; // Call the depth-first-search dfs(mat, max, visited, 0, src[0], src[1], dest); // Return the answer return max[0] + 1; } // Depth-First-Search function for // recursion and backtracking public static void dfs( int [,] mat, int [] max, bool [,] visited, int len, int i, int j, int [] dest) { // Return if current node is already // visited or it is out of bounds if (i < 0 || j < 0 || i == mat.GetLength(0) || j == mat.GetLength(1)|| visited[i, j]) return ; // If reached the destination // then update maximum length if (i == dest[0] && j == dest[1]) { // Update max max[0] = Math.Max(max[0], len); return ; } // Mark current node as visited visited[i, j] = true ; // Recursive call in all // the four directions dfs(mat, max, visited, len + 1, i, j - 1, dest); dfs(mat, max, visited, len + 1, i + 1, j, dest); dfs(mat, max, visited, len + 1, i - 1, j, dest); dfs(mat, max, visited, len + 1, i, j + 1, dest); // Mark current cell as unvisited visited[i, j] = false ; } // Driver code public static void Main() { int [,] mat = { { 5, 6, 7, 8 }, { 4, 1, 0, 9 }, { 3, 2, 11, 10 } }; int [] src = { 1, 1 }; int [] dest = { 2, 2 }; Console.Write(longestPath(mat, src, dest)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript implementation for the above approach // Depth-First-Search function for // recursion and backtracking function dfs(mat, maxi, visited, len, i, j, dest) { // Return if current node is already // visited or it is out of bounds if (i < 0 || j < 0 || i == mat.length || j == mat[0].length || visited[i][j]) return ; // If reached the destination // then update maximum length if (i == dest[0] && j == dest[1]) { // Update max maxi[0] = Math.max(maxi[0], len); return ; } // Mark current node as visited visited[i][j] = true ; // Recursive call in all // the four directions dfs(mat, maxi, visited, len + 1, i, j - 1, dest); dfs(mat, maxi, visited, len + 1, i + 1, j, dest); dfs(mat, maxi, visited, len + 1, i - 1, j, dest); dfs(mat, maxi, visited, len + 1, i, j + 1, dest); // Mark current cell as unvisited visited[i][j] = false ; } // Function to find the length of // the longest path between two nodes function longestPath(mat, src, dest) { // Initialize a variable to // calculate longest path let maxi = new Array(1); maxi[0] = 0; // Number of rows let N = mat.length; // Number of columns let M = mat[0].length; // Initialize a boolean matrix to // keep track of the cells visited let visited = new Array(N).fill(0).map(() => new Array(M).fill(0)); // Call the depth-first-search dfs(mat, maxi, visited, 0, src[0], src[1], dest); // Return the answer return maxi[0] + 1; } // Driver code let mat = [[5, 6, 7, 8], [4, 1, 0, 9], [3, 2, 11, 1]]; let src = [1, 1]; let dest = [2, 2]; document.write(longestPath(mat, src, dest)); // This code is contributed by gfgking </script> |
11
Time Complexity: O(N * M)
Auxiliary Space: O(N * M)