C++で最大長のスネークシーケンスを見つける

コンセプト

与えられた数字のグリッドに関して、最大長のスネークシーケンスを決定し、それを表示します。最大長のスネークシーケンスが複数存在する場合は、それらのいずれかを表示することが確認されています。

実際には、スネークシーケンスはグリッド内の隣接する数字で構成されているため、各数字について、右側の数字またはその下の数字は+1または-1の値になります。ここで、たとえば、グリッド内の位置（a、b）にいる場合、その数が±1の場合は右に移動できます（a、b + 1）、またはその数の場合は下に移動できます（a + 1、b）は±1です。

たとえば、

10, 7, 6, 3
9, 8, 7, 6
8, 4, 2, 7
2, 2, 2, 8

上記のグリッドでは、最大のスネークシーケンスは次のとおりです：（10、9、8、7、6、7、8）

下の図は、考えられるすべてのパスを示しています-

10  7  →6   3
↓   ↓   ↓
9 → 8 → 7→ 6
↓↓
8 4 2 7
↓
2 2 2 8

メソッド

ここでの概念は、動的計画法を実装することです。マトリックスの各セルに関して、現在のセルで終わるヘビの最長の長さを維持します。これで、最長のスネークシーケンスが最大値になります。ここで、最も長い値のセルはヘビの尻尾に対応します。ヘビを印刷するには、尾からヘビの頭までバックトラックする必要があります。 T [a] [b]がセル（a、b）で終わるヘビの最大長を表すと仮定すると、与えられた行列Mに対して、動的計画法の関係は-

T[0][0] = 0
T[a][b] = max(T[a][b], T[a][b – 1] + 1) if M[a][b] = M[a][b – 1] ± 1
T[a][b] = max(T[a][b], T[a – 1][b] + 1) if M[a][b] = M[a – 1][b] ± 1

例

// C++ program to find maximum length
// Snake sequence and print it
#include <bits/stdc++.h>
using namespace std;
#define M 4
#define N 4
struct Point{
   int X, Y;
};
// Shows function to find maximum length Snake sequence path
// (a, b) corresponds to tail of the snake
list<Point> findPath(int grid1[M][N], int mat1[M][N],
int a, int b){
   list<Point> path1;
   Point pt1 = {a, b};
   path1.push_front(pt1);
   while (grid1[a][b] != 0){
      if (a > 0 &&
      grid1[a][b] - 1 == grid1[a - 1][b]){
         pt1 = {a - 1, b};
         path1.push_front(pt1);
         a--;
      }
      else if (b > 0 &&
      grid1[a][b] - 1 == grid1[a][b - 1]){
         pt1 = {a, b - 1};
         path1.push_front(pt1);
         b--;
      }
   }
   return path1;
}
// Shows function to find maximum length Snake sequence
void findSnakeSequence(int mat1[M][N]){
   // Shows table to store results of subproblems
   int lookup1[M][N];
   // Used to initialize by 0
   memset(lookup1, 0, sizeof lookup1);
   // Used to store maximum length of Snake sequence
   int max_len1 = 0;
   // Used to store cordinates to snake's tail
   int max_row1 = 0;
   int max_col1 = 0;
   // Used to fill the table in bottom-up fashion
   for (int a = 0; a < M; a++){
      for (int b = 0; b < N; b++){
         // Perform except for (0, 0) cell
         if (a || b){
            // look above
            if (a > 0 &&
            abs(mat1[a - 1][b] - mat1[a][b]) == 1){
               lookup1[a][b] = max(lookup1[a][b],
               lookup1[a - 1][b] + 1);
            if (max_len1 < lookup1[a][b]){
               max_len1 = lookup1[a][b];
               max_row1 = a, max_col1 = b;
            }
         }
         // look left
         if (b > 0 &&
         abs(mat1[a][b - 1] - mat1[a][b]) == 1){
            lookup1[a][b] = max(lookup1[a][b],
            lookup1[a][b - 1] + 1);
            if (max_len1 < lookup1[a][b]){
               max_len1 = lookup1[a][b];
               max_row1 = a, max_col1 = b;
            }
         }
      }
   }
}
cout << "Maximum length of Snake sequence is: "
<< max_len1 << endl;
// Determine maximum length Snake sequence path
list<Point> path1 = findPath(lookup1, mat1, max_row1,
max_col1);
cout << "Snake sequence is:";
for (auto it = path1.begin(); it != path1.end(); it++)
cout << endl << mat1[it->X][it->Y] << " ("<< it->X << ", " << it->Y << ")" ;}
// Driver code
int main(){
   int mat1[M][N] ={{10, 7, 6, 3},{9, 8, 7, 6},{8, 4, 2, 7},{2, 2, 2, 8},};
   findSnakeSequence(mat1);
   return 0;
}

出力

Maximum length of Snake sequence is: 6
Snake sequence is:
10 (0, 0)
9 (1, 0)
8 (1, 1)
7 (1, 2)
6 (1, 3)
7 (2, 3)
8 (3, 3)