নির্দিষ্ট শুরুর ক্যারেক্টার থেকে সর্বোচ্চ ধারাবাহিক পথ

বিভিন্ন ক্যারেক্টারের একটি ম্যাট্রিক্স দেওয়া আছে। একটি ক্যারেক্টার থেকে শুরু করে বর্তমান ক্যারেক্টারের চেয়ে বড় এবং পরপর kolejের ক্যারেক্টার traversé করে সর্বোচ্চ দৈর্ঘ্যের পথ খুঁজে বের করতে হবে।

সর্বোচ্চ পথ খুঁজে বের করতে গভীরতা-প্রথম অনুসন্ধান (DFS) অ্যালগরিদম ব্যবহার করা হবে। DFS-এর সময় কিছু উপসমস্যা বারবার দেখা দিতে পারে। তাদের পুনরাবৃত্তি এড়াতে ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করা হবে।

ইনপুট এবং আউটপুট

ইনপুট: উপরের ম্যাট্রিক্স এবং শুরুর বিন্দু। এখানে শুরুর বিন্দু 'e'।
আউটপুট:
Enter Starting Point (a-i): e
Maximum consecutive path: 5

অ্যালগরিদম

findLongestLen(i, j, prev)

ইনপুট: অবস্থান i, j এবং পূর্বের ক্যারেক্টার।
আউটপুট: সর্বোচ্চ দৈর্ঘ্য।

শুরু
  যদি (i, j) অবস্থান বৈধ না হয় বা prev এবং matrix[i,j] সন্নিহিত না হয়, তবে
    ফেরত দিন 0
  যদি longestPath[i, j] ইতিমধ্যে ভরা থাকে, তবে
    ফেরত দিন longestPath[i, j]
  len := 0
  এর সবচেয়ে নিকটবর্তী ৮টি কক্ষ k জন্য, করুন
    len := len এবং (1 + findLongestLen(i + x[k], j + y[k], matrix[i, j])) এর মধ্যে সর্বোচ্চ
  শেষ
  longestPath[i, j] := len
  ফেরত দিন len
শেষ

getLen(start)

ইনপুট: শুরুর বিন্দু।
আউটপুট: সর্বোচ্চ দৈর্ঘ্য।

শুরু
  ম্যাট্রিক্সের সকল সারি r জন্য, করুন
    সকল কলাম c জন্য, করুন
      যদি matrix[i, j] = start হয়, তবে
        সকল সন্নিহিত কক্ষ k জন্য, করুন
          len := len এবং (1 + findLongestLen(i + x[k], j + y[k], matrix[i, j]))) এর মধ্যে সর্বোচ্চ
        শেষ
      শেষ
    শেষ
  শেষ
  ফেরত দিন len
শেষ

উদাহরণ (C++)

#include <iostream>
#define ROW 3
#define COL 3
using namespace std;

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) return false;
  return true;
}

bool isadjacent(char previous, char current) {
  return ((current - previous) == 1);
}

int findLongestLen(int i, int j, char prev) {
  if (!isvalid(i, j) || !isadjacent(prev, mat[i][j])) return 0;
  if (longestPath[i][j] != -1) return longestPath[i][j];

  int len = 0;
  for (int k=0; k<8; k++)
    len = max(len, 1 + findLongestLen(i + x[k], j + y[k], mat[i][j]));

  return longestPath[i][j] = len;
}

int getLen(char start) {
  for(int i = 0; i> start;
  cout << "Maximum consecutive path: " << getLen(start);
  return 0;
}

আউটপুট

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