Find the longest possible route in a matrix
Given a rectangular path in the form of a binary matrix, find the length of the longest possible route from source to destination by moving to only non-zero adjacent positions, i.e., We can form the route from positions having their value as 1. Note there should not be any cycles in the output path.
For example, the longest path from source cell (0, 0) to destination cell (5, 7) has length 22 for the following matrix.
(0, 0) —> (1, 0) —> (2, 0) —> (2, 1) —> (2, 2) —> (1, 2) —> (0, 2) —> (0, 3) —> (0, 4) —> (1, 4) —> (1, 5) —> (2, 5) —> (2, 4) —> (3, 4) —> (4, 4) —> (5, 4) —> (5, 5) —> (5, 6) —> (4, 6) —> (4, 7) —> (4, 8) —> (5, 8) —> (5, 7)
We can use backtracking to solve this problem. We start from the given source cell in the matrix and explore all four paths possible and recursively check if they will lead to the destination or not. We have to keep track of the current cell’s distance from the source and update the value of the longest path found so far on reaching the destination cell. If a path doesn’t reach the destination or explored all possible routes from the current cell, backtrack. To make sure that the path is simple and doesn’t contain any cycles, keep track of cells involved in the current path in a matrix, and before exploring any cell, ignore the cell if it is already covered in the current path.
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include <iostream> #include <vector> #include <cstring> using namespace std; // Check if it is possible to go to position (x, y) from // the current position. The function returns false if the cell // has a value 0, or it is already visited. bool isSafe(vector<vector<int>> &mat, vector<vector<bool>> &visited, int x, int y) { return (x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size()) && mat[x][y] == 1 && !visited[x][y]; } // Find the longest possible route in a matrix `mat` from the source cell // (i, j) to destination cell (x, y). // `max_dist` —> keep track of the length of the longest path from source to // destination. It is passed by reference. // `dist` —> length of the path from the source cell to the current cell (i, j). void findLongestPath(vector<vector<int>> &mat, vector<vector<bool>> &visited, int i, int j, int x, int y, int &max_dist, int dist) { // if the destination is not possible from the current cell if (mat[i][j] == 0) { return; } // if the destination is found, update `max_dist` if (i == x && j == y) { max_dist = max(dist, max_dist); return; } // set (i, j) cell as visited visited[i][j] = 1; // go to the bottom cell if (isSafe(mat, visited, i + 1, j)) { findLongestPath(mat, visited, i + 1, j, x, y, max_dist, dist + 1); } // go to the right cell if (isSafe(mat, visited, i, j + 1)) { findLongestPath(mat, visited, i, j + 1, x, y, max_dist, dist + 1); } // go to the top cell if (isSafe(mat, visited, i - 1, j)) { findLongestPath(mat, visited, i - 1, j, x, y, max_dist, dist + 1); } // go to the left cell if (isSafe(mat, visited, i, j - 1)) { findLongestPath(mat, visited, i, j - 1, x, y, max_dist, dist + 1); } // backtrack: remove (i, j) from the visited matrix visited[i][j] = 0; } // Wrapper over findLongestPath() function int findLongestPathLength(vector<vector<int>> &mat, pair<int, int> &src, pair<int, int> &dest) { // base case: invalid input if (mat.size() == 0 || mat[src.first][src.second] == 0 || mat[dest.first][dest.second] == 0) { return -1; } // `M × N` matrix int M = mat.size(); int N = mat[0].size(); // construct an `M × N` matrix to keep track of visited cells vector<vector<bool>> visited; visited.resize(M, vector<bool>(N)); int max_dist = 0; findLongestPath(mat, visited, src.first, src.second, dest.first, dest.second, max_dist, 0); return max_dist; } int main() { // input matrix vector<vector<int>> mat = { { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 }, { 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 }, { 1, 0, 0, 0, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 }, { 1, 0, 0, 0, 1, 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1, 1, 0, 0, 1, 1 }, { 1, 1, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 } }; // (0, 0) are the source cell, and (5, 7) are the destination cell coordinates pair<int, int> src = make_pair(0, 0); pair<int, int> dest = make_pair(5, 7); cout << "The Maximum length path is " << findLongestPathLength(mat, src, dest); return 0; } |
Output:
The maximum length path is 22
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
class Main { // Check if it is possible to go to position (x, y) from // the current position. The function returns false if the cell // is invalid, has a value 0, or it is already visited. private static boolean isSafe(int[][] mat, boolean[][] visited, int x, int y) { return (x >= 0 && x < mat.length && y >= 0 && y < mat[0].length) && mat[x][y] == 1 && !visited[x][y]; } // Find the longest possible route in a matrix `mat` from the source cell // (i, j) to destination cell (x, y). // `max_dist` —> keep track of the length of the longest path from source to // destination. // `dist` —> length of the path from the source cell to the current cell (i, j). public static int findLongestPath(int[][] mat, boolean[][] visited, int i, int j, int x, int y, int max_dist, int dist) { // if the destination is not possible from the current cell if (mat[i][j] == 0) { return 0; } // if the destination is found, update `max_dist` if (i == x && j == y) { return Integer.max(dist, max_dist); } // set (i, j) cell as visited visited[i][j] = true; // go to the bottom cell if (isSafe(mat, visited, i + 1, j)) { max_dist = findLongestPath(mat, visited, i + 1, j, x, y, max_dist, dist + 1); } // go to the right cell if (isSafe(mat, visited, i, j + 1)) { max_dist = findLongestPath(mat, visited, i, j + 1, x, y, max_dist, dist + 1); } // go to the top cell if (isSafe(mat, visited, i - 1, j)) { max_dist = findLongestPath(mat, visited, i - 1, j, x, y, max_dist, dist + 1); } // go to the left cell if (isSafe(mat, visited, i, j - 1)) { max_dist = findLongestPath(mat, visited, i, j - 1, x, y, max_dist, dist + 1); } // backtrack: remove (i, j) from the visited matrix visited[i][j] = false; return max_dist; } // Wrapper over findLongestPath() function public static int findLongestPathLength(int[][] mat, int i, int j, int x, int y) { // base case: invalid input if (mat == null || mat.length == 0 || mat[i][j] == 0 || mat[x][y] == 0) { return -1; } // `M × N` matrix int M = mat.length; int N = mat[0].length; // construct an `M × N` matrix to keep track of visited cells boolean[][] visited= new boolean[M][N]; // (i, j) are the source cell, and (x, y) are the destination // cell coordinates return findLongestPath(mat, visited, i, j, x, y, 0, 0); } public static void main(String[] args) { // input matrix int mat[][] = { { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 }, { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 }, { 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 }, { 1, 0, 0, 0, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 }, { 1, 0, 0, 0, 1, 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1, 1, 0, 0, 1, 1 }, { 1, 1, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 } }; // (0, 0) are the source cell, and (5, 7) are the destination // cell coordinates int max_dist = findLongestPathLength(mat, 0, 0, 5, 7); System.out.println("The maximum length path is " + max_dist); } } |
Output:
The maximum length path is 22
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
# Check if it is possible to go to position (x, y) from # the current position. The function returns false if the cell # is invalid, has a value 0, or it is already visited. def isSafe(mat, visited, x, y): return 0 <= x < len(mat) and 0 <= y < len(mat[0]) and \ not (mat[x][y] == 0 or visited[x][y]) # Find the longest possible route in a matrix `mat` from the source cell (i, j) # to destination cell `dest`. # `max_dist` —> keep track of the length of the longest path from source to destination # `dist` —> length of the path from the source cell to the current cell (i, j) def findLongestPath(mat, visited, i, j, dest, max_dist=0, dist=0): # if the destination is not possible from the current cell if mat[i][j] == 0: return 0 # if the destination is found, update `max_dist` if (i, j) == dest: return max(dist, max_dist) # set (i, j) cell as visited visited[i][j] = 1 # go to the bottom cell if isSafe(mat, visited, i + 1, j): max_dist = findLongestPath(mat, visited, i + 1, j, dest, max_dist, dist + 1) # go to the right cell if isSafe(mat, visited, i, j + 1): max_dist = findLongestPath(mat, visited, i, j + 1, dest, max_dist, dist + 1) # go to the top cell if isSafe(mat, visited, i - 1, j): max_dist = findLongestPath(mat, visited, i - 1, j, dest, max_dist, dist + 1) # go to the left cell if isSafe(mat, visited, i, j - 1): max_dist = findLongestPath(mat, visited, i, j - 1, dest, max_dist, dist + 1) # backtrack: remove (i, j) from the visited matrix visited[i][j] = 0 return max_dist # Wrapper over findLongestPath() function def findLongestPathLength(mat, src, dest): # get source cell (i, j) i, j = src # get destination cell (x, y) x, y = dest # base case if not mat or len(mat) == 0 or mat[i][j] == 0 or mat[x][y] == 0: return 0 # `M × N` matrix (M, N) = (len(mat), len(mat[0])) # construct an `M × N` matrix to keep track of visited cells visited = [[0 for x in range(N)] for y in range(M)] # (i, j) are the source cell coordinates, and (x, y) are the # destination cell coordinates return findLongestPath(mat, visited, i, j, dest) if __name__ == '__main__': # input matrix mat = [ [1, 0, 1, 1, 1, 1, 0, 1, 1, 1], [1, 0, 1, 0, 1, 1, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1, 0, 1, 0, 1], [0, 0, 0, 0, 1, 0, 0, 1, 0, 0], [1, 0, 0, 0, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 0], [1, 0, 0, 0, 1, 0, 0, 1, 0, 1], [1, 0, 1, 1, 1, 1, 0, 0, 1, 1], [1, 1, 0, 0, 1, 0, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 0, 1, 0, 0] ] src = (0, 0) dest = (5, 7) print("The maximum length path is", findLongestPathLength(mat, src, dest)) |
Output:
The maximum length path is 22
The time complexity of the above solution is exponential and requires additional space for the recursion (call stack).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)