Find the longest path in a matrix with given constraints - GeeksforGeeks

Find the longest path in a matrix with given constraints - GeeksforGeeks

Find the longest path in a matrix with given constraints Given a n*n matrix where numbers all numbers are distinct and are distributed from range 1 to n2, find the maximum length path (starting from any cell) such that all cells along the path are 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 adjacen Example: Input: mat[][] = {{1, 2, 9} {5, 3, 8} {4, 6, 7}} Output: 4 The longest path is 6-7-8-9. We strongly recommend you to minimize your browser and try this yourself first. 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.

Read full article from Find the longest path in a matrix with given constraints - GeeksforGeeks