给定一个n*n矩阵，其中所有数字都是不同的，求出最大长度路径（从任何单元格开始），这样路径上的所有单元格都以1为差的递增顺序排列。 我们可以从一个给定的单元（i，j）向4个方向移动，也就是说，我们可以在相邻单元的差值为1的情况下移动到（i+1，j）或（i，j+1）或（i-1，j）或（i，j-1）。 例子：
null
Input: mat[][] = {{1, 2, 9} {5, 3, 8} {4, 6, 7}}Output: 4The longest path is 6-7-8-9.
这个想法很简单，我们计算从每个细胞开始的最长路径。一旦我们计算了所有单元的最长路径，我们将返回所有最长路径的最大值。这种方法的一个重要观察结果是许多重叠的子问题。因此，这个问题可以用动态规划来优化解决。 下面是基于动态编程的实现，它使用一个查找表dp[][]来检查问题是否已经解决。
C++
// C++ program to find the longest path in a matrix // with given constraints #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]) { 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]; // To store the path lengths in all the four directions int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN; // 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])) x = 1 + findLongestFromACell(i, j + 1, mat, dp); if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1])) y = 1 + findLongestFromACell(i, j - 1, mat, dp); if (i > 0 && (mat[i][j] + 1 == mat[i - 1][j])) z = 1 + findLongestFromACell(i - 1, j, mat, dp); if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1][j])) w = 1 + findLongestFromACell(i + 1, j, mat, dp); // If none of the adjacent fours is one greater we will take 1 // otherwise we will pick maximum from all the four directions return dp[i][j] = max(x, max(y, max(z, max(w, 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; } |
JAVA
// Java program to find the longest path in a matrix // with given constraints class GFG { public static int n = 3 ; // Function that returns length of the longest path // beginning with mat[i][j] // This function mainly uses lookup table dp[n][n] static int findLongestFromACell( int i, int j, int mat[][], int dp[][]) { // 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]; // To store the path lengths in all the four directions int x = Integer.MIN_VALUE, y = Integer.MIN_VALUE, z = Integer.MIN_VALUE, w = Integer.MIN_VALUE; // 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 ])) x = dp[i][j] = 1 + findLongestFromACell(i, j + 1 , mat, dp); if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1 ])) y = dp[i][j] = 1 + findLongestFromACell(i, j - 1 , mat, dp); if (i > 0 && (mat[i][j] + 1 == mat[i - 1 ][j])) z = dp[i][j] = 1 + findLongestFromACell(i - 1 , j, mat, dp); if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1 ][j])) w = dp[i][j] = 1 + findLongestFromACell(i + 1 , j, mat, dp); // If none of the adjacent fours is one greater we will take 1 // otherwise we will pick maximum from all the four directions return dp[i][j] = Math.max(x, Math.max(y, Math.max(z, Math.max(w, 1 )))); } // Function that returns length of the longest path // beginning with any cell static int finLongestOverAll( int mat[][]) { // Initialize result int result = 1 ; // Create a lookup table and fill all entries in it as -1 int [][] dp = new int [n][n]; for ( int i = 0 ; i < n; i++) for ( int j = 0 ; j < n; j++) dp[i][j] = - 1 ; // 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 = Math.max(result, dp[i][j]); } } return result; } // driver program public static void main(String[] args) { int mat[][] = { { 1 , 2 , 9 }, { 5 , 3 , 8 }, { 4 , 6 , 7 } }; System.out.println( "Length of the longest path is " + finLongestOverAll(mat)); } } // Contributed by Pramod Kumar |
Python3
# Python3 program to find the longest path in a matrix # with given constraints n = 3 # Returns length of the longest path beginning with mat[i][j]. # This function mainly uses lookup table dp[n][n] def findLongestFromACell(i, j, mat, dp): # Base case if (i< 0 or i> = n or j< 0 or j> = n): return 0 # If this subproblem is already solved if (dp[i][j] ! = - 1 ): return dp[i][j] # To store the path lengths in all the four directions x, y, z, w = - 1 , - 1 , - 1 , - 1 # 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 and ((mat[i][j] + 1 ) = = mat[i][j + 1 ])): x = 1 + findLongestFromACell(i, j + 1 , mat, dp) if (j> 0 and (mat[i][j] + 1 = = mat[i][j - 1 ])): y = 1 + findLongestFromACell(i, j - 1 , mat, dp) if (i> 0 and (mat[i][j] + 1 = = mat[i - 1 ][j])): z = 1 + findLongestFromACell(i - 1 , j, mat, dp) if (i<n - 1 and (mat[i][j] + 1 = = mat[i + 1 ][j])): w = 1 + findLongestFromACell(i + 1 , j, mat, dp) # If none of the adjacent fours is one greater we will take 1 # otherwise we will pick maximum from all the four directions dp[i][j] = max (x, max (y, max (z, max (w, 1 )))) return dp[i][j] # Returns length of the longest path beginning with any cell def finLongestOverAll(mat): result = 1 # Initialize result # Create a lookup table and fill all entries in it as -1 dp = [[ - 1 for i in range (n)] for i in range (n)] # Compute longest path beginning from all cells for i in range (n): for j in range (n): if (dp[i][j] = = - 1 ): findLongestFromACell(i, j, mat, dp) # Update result if needed result = max (result, dp[i][j]); return result # Driver program mat = [[ 1 , 2 , 9 ], [ 5 , 3 , 8 ], [ 4 , 6 , 7 ]] print ( "Length of the longest path is " , finLongestOverAll(mat)) # this code is improved by sahilshelangia |
Javascript
<script> // JavaScript program to find the longest path in a matrix // with given constraints let n = 3; // Returns length of the longest path beginning with mat[i][j]. // This function mainly uses lookup table dp[n][n] function findLongestFromACell( i, j, mat, dp){ 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]; // To store the path lengths in all the four directions let x,y,z,w; x = -1; y = -1; z = -1 w = -1; // 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])) x = 1 + findLongestFromACell(i, j + 1, mat, dp); if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1])) y = 1 + findLongestFromACell(i, j - 1, mat, dp); if (i > 0 && (mat[i][j] + 1 == mat[i - 1][j])) z = 1 + findLongestFromACell(i - 1, j, mat, dp); if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1][j])) w = 1 + findLongestFromACell(i + 1, j, mat, dp); // If none of the adjacent fours is one greater we will take 1 // otherwise we will pick maximum from all the four directions dp[i][j] = Math.max(x, Math.max(y, Math.max(z, Math.max(w, 1)))); return dp[i][j]; } // Returns length of the longest path beginning with any cell function finLongestOverAll( mat){ let result = 1; // Initialize result // Create a lookup table and fill all entries in it as -1 var dp = []; for ( var y = 0; y < n; y++ ) { dp[ y ] = []; for ( var x = 0; x < n; x++ ) { dp[ y ][ x ] = -1; } } // Compute longest path beginning from all cells for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (dp[i][j] == -1) findLongestFromACell(i, j, mat, dp); // Update result if needed result = Math.max(result, dp[i][j]); } } return result; } // Driver program let mat = [[ 1, 2, 9 ], [ 5, 3, 8 ], [ 4, 6, 7 ]]; document.write( "Length of the longest path is " ); document.write( finLongestOverAll(mat)); </script> |
C#
// C# program to find the longest path // in a matrix with given constraints using System; class GFG { public static int n = 3; // Function that returns length of // the longest path beginning with mat[i][j] // This function mainly uses lookup // table dp[n][n] public static int findLongestFromACell( int i, int j, int [][] mat, int [][] dp) { // 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]; } // To store the path lengths in all the four directions int x = int .MinValue, y = int .MinValue, z = int .MinValue, w = int .MinValue; // 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])) { x = dp[i][j] = 1 + findLongestFromACell(i, j + 1, mat, dp); } if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1])) { y = dp[i][j] = 1 + findLongestFromACell(i, j - 1, mat, dp); } if (i > 0 && (mat[i][j] + 1 == mat[i - 1][j])) { z = dp[i][j] = 1 + findLongestFromACell(i - 1, j, mat, dp); } if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1][j])) { w = dp[i][j] = 1 + findLongestFromACell(i + 1, j, mat, dp); } // If none of the adjacent fours is one greater we will take 1 // otherwise we will pick maximum from all the four directions dp[i][j] = Math.Max(x, Math.Max(y, Math.Max(z, Math.Max(w, 1)))); return dp[i][j]; } // Function that returns length of the // longest path beginning with any cell public static int finLongestOverAll( int [][] mat) { // Initialize result int result = 1; // Create a lookup table and fill // all entries in it as -1 int [][] dp = RectangularArrays.ReturnRectangularIntArray(n, n); for ( int i = 0; i < n; i++) { for ( int j = 0; j < n; j++) { dp[i][j] = -1; } } // 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 = Math.Max(result, dp[i][j]); } } return result; } public static class RectangularArrays { public static int [][] ReturnRectangularIntArray( int size1, int size2) { int [][] newArray = new int [size1][]; for ( int array1 = 0; array1 < size1; array1++) { newArray[array1] = new int [size2]; } return newArray; } } // Driver Code public static void Main( string [] args) { int [][] mat = new int [][] { new int [] { 1, 2, 9 }, new int [] { 5, 3, 8 }, new int [] { 4, 6, 7 } }; Console.WriteLine( "Length of the longest path is " + finLongestOverAll(mat)); } } // This code is contributed by Shrikant13 |
输出：
Length of the longest path is 4
上述解的时间复杂度为O（n） 2. ).乍一看可能更像。如果我们仔细观察，我们可以注意到dp[i][j]的所有值只计算一次。 本文由 埃克塔·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
