在給定約束條件下找到矩陣中的最長路徑 · GeeksForGeeks 中文系列教程

# 在給定約束條件下找到矩陣中的最長路徑 > 原文： [https://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/](https://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/) 給定一個 n * n 矩陣，其中所有數字都是不同的，請找到最大長度路徑（從任何單元格開始），以使該路徑上的所有單元格都以遞增順序排列，相差 1。我們可以從給定的像元（i，j）向 4 個方向移動，即我們可以移動到（i + 1，j）或（i，j + 1）或（i-1，j）或（i，j -1），條件是相鄰像元的差為 1。 **示例**： ``` Input: mat[][] = {{1, 2, 9} {5, 3, 8} {4, 6, 7}} Output: 4 The longest path is 6-7-8-9\. ``` 這個想法很簡單，我們計算從每個單元格開始的最長路徑。一旦計算出所有單元格的最長，就返回所有最長路徑的最大值。這種方法的一個重要發現是許多重疊的子問題。因此，可以使用動態編程來最佳解決該問題。以下是基于動態編程的實現，該實現使用查找表 dp [] []來檢查問題是否已解決。 ## C/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 // 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 ```py # 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 ``` ## C# ```cs // 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]的所有值僅計算一次。本文由 [Ekta Goel](https://www.linkedin.com/pub/ekta-goel/75/12a/3a6) 提供。如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請發表評論