কনসেপ্ট
একটি সংখ্যার গ্রিড দেওয়া আছে। সর্বোচ্চ দৈর্ঘ্যের স্নেক সিকোয়েন্স খুঁজে বের করুন এবং তা প্রদর্শন করুন। একাধিক স্নেক সিকোয়েন্স থাকলে যেকোনো একটি দেখান।
স্নেক সিকোয়েন্স হল গ্রিডের আডজেসেন্ট সংখ্যাগুলোর সমষ্টি যাতে প্রতিটি সংখ্যার ডানে বা নিচের সংখ্যা তার মান থেকে +1 বা -1 হয়। অর্থাৎ লোকেশন (a, b)-এ থাকলে (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)
পদ্ধতি
ডাইনামিক প্রোগ্রামিং ব্যবহার করুন। প্রতিটি সেলের জন্য স্নেকের সর্বোচ্চ দৈর্ঘ্য সংরক্ষণ করুন যা ওই সেলে শেষ হয়। সর্বোচ্চ মান্বালা সেল স্নেকের টেইল (Tail) হবে। স্নেক প্রিন্ট করতে টেইল থেকে হেড পর্যন্ত ব্যাকট্র্যাক (backtrack) করুন।
DP সম্পর্ক: T[a][b] = ম্যাক্স(T[a][b], T[a][b-1]+1) যদি M[a][b] = M[a][b-1] ± 1, এবং T[a][b] = ম্যাক্স(T[a][b], T[a-1][b]+1) যদি M[a][b] = M[a-1][b] ± 1।
উদাহরণ (C++ কোড)
// C++ প্রোগ্রাম: সর্বোচ্চ দৈর্ঘ্যের স্নেক সিকোয়েন্স খুঁজে বের ও প্রিন্ট করার জন্য
#include <bits/stdc++.h>
using namespace std;
#define M 4
#define N 4
struct Point { int X, Y; };
// স্নেকের পাথ খুঁজে বের করার ফাংশন (a,b) = টেইল
list findPath(int grid1[M][N], int mat1[M][N], int a, int b) {
list 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;
}
// স্নেক সিকোয়েন্স খুঁজে বের করার ফাংশন
void findSnakeSequence(int mat1[M][N]) {
int lookup1[M][N];
memset(lookup1, 0, sizeof lookup1);
int max_len1 = 0, max_row1 = 0, max_col1 = 0;
// বটম-আপ টেবিল পূরণ
for (int a = 0; a < M; a++) {
for (int b = 0; b < N; b++) {
if (a || b) { // (0,0) বাদ
// উপরের সেল চেক
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;
}
}
// বামের সেল চেক
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 << "স্নেক সিকোয়েন্সের সর্বোচ্চ দৈর্ঘ্য: " << max_len1 << endl;
// পাথ নির্ণয়
list path1 = findPath(lookup1, mat1, max_row1, max_col1);
cout << "স্নেক সিকোয়েন্স: ";
for (auto it = path1.begin(); it != path1.end(); it++)
cout << endl << mat1[it->X][it->Y] << " (" << it->X << ", " << it->Y << ")";
}
// ড্রাইভার কোড
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;
}
আউটপুট
স্নেক সিকোয়েন্সের সর্বোচ্চ দৈর্ঘ্য: 6 স্নেক সিকোয়েন্স: 10 (0, 0) 9 (1, 0) 8 (1, 1) 7 (1, 2) 6 (1, 3) 7 (2, 3) 8 (3, 3)
