用 C++ 查詢給定約束矩陣中最長路徑

假設我們有一個 n 階方陣。它有所有不同的元素。因此，我們必須找到最長的路徑，這樣路徑上的所有單元格按升序排列，且差值為 1。我們從一個單元格可以移動到四個方向。左、右、上、下。因此，如果矩陣如下：

那麼輸出將是 4。因為最長路徑是 6→7→8→ 9

為了解決這個問題，我們將遵循這個思路。我們將計算以每個單元格開頭最長的路徑。一旦我們獲得了所有單元格最長的路徑，我們返回所有最長路徑的最大值。

此方法中一個重要的觀察是許多重疊的子問題。因此，可以使用動態規劃來解決該問題。在這裡，我們將使用查詢表 dp[][] 來檢查某個問題是否已經解決。

示例

#include <iostream>
#define n 3
using namespace std;
int getLongestPathLengthUtil(int i, int j, int matrix[n][n], int table[n][n]) {
   if (i < 0 || i >= n || j < 0 || j >= n)
   return 0;
   if (table[i][j] != -1)
      return table[i][j];
   int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN;
   if (j < n - 1 && ((matrix[i][j] + 1) == matrix[i][j + 1]))
      x = 1 + getLongestPathLengthUtil(i, j + 1, matrix, table);
   if (j > 0 && (matrix[i][j] + 1 == matrix[i][j - 1]))
      y = 1 + getLongestPathLengthUtil(i, j - 1, matrix, table);
   if (i > 0 && (matrix[i][j] + 1 == matrix[i - 1][j]))
      z = 1 + getLongestPathLengthUtil(i - 1, j, matrix, table);
   if (i < n - 1 && (matrix[i][j] + 1 == matrix[i + 1][j]))
      w = 1 + getLongestPathLengthUtil(i + 1, j, matrix, table);
      return table[i][j] = max(x, max(y, max(z, max(w, 1))));
}
int getLongestPathLength(int matrix[n][n]) {
   int result = 1;
   int table[n][n];
   for(int i = 0; i < n; i++)
   for(int j = 0; j < n; j++)
   table[i][j] = -1;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         if (table[i][j] == -1)
         getLongestPathLengthUtil(i, j, matrix, table);
         result = max(result, table[i][j]);
      }
   }
   return result;
}
int main() {
   int mat[n][n] = { { 1, 2, 9 },
   { 5, 3, 8 },
   { 4, 6, 7 } };
   cout << "Length of the longest path is "<< getLongestPathLength(mat);
}

輸出

Length of the longest path is 4

Arnab Chakraborty

更新於：2019-12-18

454 瀏覽量

開啟您的 事業

透過完成課程獲得認證

開始學習