C++で指定された開始文字からの最長の連続パスの長さを検索します

異なる文字のマトリックスが与えられます。 1つの文字から始めて、現在の文字よりも大きいすべての文字をトラバースすることにより、最長のパスを見つける必要があります。文字は互いに連続しています。

Eから始まります。

最長のパスを見つけるために、深さ優先探索アルゴリズムを使用します。 DFS中に、いくつかのサブ問題が複数回発生する場合があります。そのサブ問題の計算を何度も回避するために、動的計画法のアプローチを使用します。

例

#include<iostream>
#define ROW 3
#define COL 3
using namespace std;
// tool matrices to recur for adjacent cells.
int x[] = {0, 1, 1, -1, 1, 0, -1, -1};
int y[] = {1, 0, 1, 1, -1, -1, 0, -1};
int longestPath[ROW][COL];
char mat[ROW][COL] = {
   {'a','c','d'},
   {'h','b','a'},
   {'i','g','f'}
};
int max(int a, int b){
   return (a>b)?a:b;
}
bool isvalid(int i, int j){
   if (i < 0 || j < 0 || i >= ROW || j >= COL) //when i and j are in range
   return false;
   return true;
}
bool isadjacent(char previous, char current){
   return ((current - previous) == 1); //check current and previous are adjacent or not
}
int findLongestLen(int i, int j, char prev){
   if (!isvalid(i, j) || !isadjacent(prev, mat[i][j]))
      //when already included or not adjacent
      return 0;
   if (longestPath[i][j] != -1)
   return longestPath[i][j]; //subproblems are solved already
   int len = 0; // Initialize result to 0
   for (int k=0; k<8; k++) //find length of the largest path recursively
   len = max(len, 1 + findLongestLen(i + x[k], j + y[k], mat[i][j]));
      return longestPath[i][j] = len; // save the length and return
}
int getLen(char start){
   for(int i = 0; i<ROW; i++)
   for(int j = 0; j<COL; j++)
   longestPath[i][j] = -1; //set all elements to -1
   int len = 0;
   for (int i=0; i<ROW; i++){
      for (int j=0; j<COL; j++){ // check for all possible starting point
         if (mat[i][j] == start) {
            for (int k=0; k<8; k++) //for all eight adjacent cells
               len = max(len, 1 + findLongestLen(i + x[k], j + y[k], start));
            }
         }
   }
   return len;
}
int main() {
   char start;
   cout << "Enter Starting Point (a-i): "; cin >> start;
   cout << "Maximum consecutive path: " << getLen(start);
   return 0;
}

出力

Enter Starting Point (a-i): e
Maximum consecutive path: 5