নিম্নলিখিত সমস্যাটি দৈনিক সংবাদপত্রের ক্রসওয়ার্ডের একটি উদাহরণ, এখানে আমাদের একটি 2-মাত্রিক অক্ষর অ্যারে দেওয়া হয়েছে এবং সমস্যা বিবৃতিটি হল 2-মাত্রিক অক্ষর অ্যারে গোলকধাঁধা থেকে প্রদত্ত শব্দটি খুঁজে বের করা। অনুসন্ধান অ্যালগরিদম থেকে পৃথক অক্ষরগুলি খুঁজে পাওয়া অন্তর্ভুক্ত টপ-টু-বটম ,ডান-থেকে-বামে এবং তদ্বিপরীত কিন্তু তির্যক নয়।
আসুন উদাহরণ দিয়ে বোঝা যাক
ইনপুট- স্ট্রিং শব্দ-LAYS
2D স্ট্রিং[ ] - { "LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS" };
আউটপুট- 2D অক্ষর অ্যারেতে প্রদত্ত স্ট্রিংগুলির সংখ্যা:7
ব্যাখ্যা - যেমন আমাদেরকে শব্দের স্ট্রিং অ্যারে দেওয়া হয়েছে এবং সেগুলি থেকে, আমাদের "LAYS" শব্দটি খুঁজে বের করতে হবে যা যে কোনো দিকে যেমন টপ-বটম, রাইট-লেফট, বটম-টপ এবং লেফট-রাইট সার্চ করা যায়। প্রদত্ত অনুসন্ধান স্ট্রিং পাওয়া গেলে প্রতিবার কোডে কাউন্টার ফ্ল্যাগ যুক্ত হয় এবং ফলাফলের জন্য গণনা শেষে ফেরত দেওয়া হয়। উদাহরণে, আমরা দেখতে পাচ্ছি LAYS 7 বার গঠিত হয়েছে অর্থাৎ
1->L OA PYS -LAYS-> বাম থেকে ডানে
2 ->S৷ AYA OL -লেস(ডান থেকে বামে)
3->লেস টি-লেস(বাম থেকে ডানে)
4->ML VAYS- LAYS(বাম থেকে ডানে)
5->লেসা A-LAYS(বাম থেকে ডানে)
6->LA OYLS -লেস(বাম থেকে ডানে)
7->(নীচ থেকে উপরে) লাল স্তরে
ইনপুট- স্ট্রিং শব্দ- CAMP
2D স্ট্রিং[ ] - { "BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL" }
আউটপুট- 2D অক্ষর অ্যারেতে প্রদত্ত স্ট্রিংয়ের সংখ্যা:0
ব্যাখ্যা-: যেমন আমাদেরকে শব্দের স্ট্রিং অ্যারে দেওয়া হয়েছে এবং সেগুলি থেকে, আমাদের "LAYS" শব্দটি খুঁজে বের করতে হবে যা যে কোনো দিকে যেমন টপ-বটম, রাইট-লেফট, বটম-টপ এবং লেফট-রাইট সার্চ করা যায়। প্রদত্ত অনুসন্ধান স্ট্রিং পাওয়া গেলে প্রতিবার কোডে কাউন্টার ফ্ল্যাগ যুক্ত হয় এবং ফলাফলের জন্য গণনা শেষে ফেরত দেওয়া হয়। উদাহরণে, আমরা দেখতে পারি BOOK গঠিত হয়েছে 0 বার
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
- আমাদের একটি স্ট্রিং(শব্দ) এবং স্ট্রিং অ্যারে দেওয়া হয়েছে যা কিছু ইউটিলিটি ভেরিয়েবল সহ আরও প্রক্রিয়াকরণের জন্য findString() এ পাস করা হয়৷
- ম্যাট্রিক্সের অক্ষরগুলিকে তারপর ট্র্যাভার্স করা হয় এবং স্ট্রিং শুরু করার জন্য একটি অক্ষর বাছাই করা হয়৷
- যে অক্ষরটি বাছাই করা হয়েছে তার জন্য আমরা অ্যালগরিদম অনুসারে সম্ভাব্য সমস্ত দিক থেকে প্রদত্ত স্ট্রিংটির জন্য পুনরাবৃত্তিমূলকভাবে খুঁজে পাই
- যদি একটি মিল পাওয়া যায় তাহলে কাউন্টারটি বৃদ্ধি করা হয়
- প্রথম স্টার্ট অক্ষর দিয়ে শেষ করার পর, পরবর্তী অক্ষরের জন্য প্রক্রিয়াটি পুনরাবৃত্তি করা হয়
- গণনার সমষ্টি তারপর সংশ্লিষ্ট মিলগুলির সাথে গণনা করা হয়
- অন্তত চূড়ান্ত উত্তর ক্যাপচার করা হয়, এবং ফলাফল মুদ্রিত হয়।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int utilitySearch(string word, int r, int c, string arr[], int maxR, int maxC, int index) {
int count = 0;
if (r >= 0 && r <= maxR && c >= 0) {
if (c <= maxC && word[index] == arr[r][c]) {
char res = word[index];
index = index + 1;
arr[r][c] = 0;
if (word[index] == 0) {
count = 1;
} else {
count = count + utilitySearch(word, r, c + 1, arr, maxR, maxC, index);
count = count + utilitySearch(word, r, c - 1, arr, maxR, maxC, index);
count = count + utilitySearch(word, r + 1, c, arr, maxR, maxC, index);
count = count + utilitySearch(word, r - 1, c, arr, maxR, maxC, index);
}
arr[r][c] = res;
}
}
return count;
}
int findString(string word, int r, int c, string str[], int countR, int countC) {
int count = 0;
for (int i = 0; i < countR; ++i) {
for (int j = 0; j < countC; ++j) {
count = count + utilitySearch(word, i, j, str, countR - 1, countC - 1, 0);
}
}
return count;
}
int main() {
string word = "FLOOD";
string inp[] = {"FPLIOKOD","FLOODYUT","YFLOODPU","FMLOSODT","FILPOYOD", FLOOOODE " };
string str[(sizeof(inp) / sizeof( * inp))];
for (int i = 0; i < (sizeof(inp) / sizeof( * inp)); ++i) {
str[i] = inp[i];
}
cout << "Count of number of given string in 2D character array: " << findString(word, 0, 0, str, (sizeof(inp) / sizeof( * inp)), str[0].size());
return 0;
} যদি আমরা উপরের কোডটি চালাই তবে এটি নিম্নলিখিত আউটপুট −
উৎপন্ন করবেআউটপুট
Count of number of given string in 2D character array: 6
