২ডি ক্যারেক্টার অ্যারেতে নির্দিষ্ট স্ট্রিংর বার্তা গণনা (C++)

নিচের সমস্যাটি দৈনিক পত্রিকার ক্রসওয়ার্ডের একটি উদাহরণ। এখানে একটি ২-ডাইমেনশনাল ক্যারেক্টার অ্যারে দেওয়া আছে এবং একটি নির্দিষ্ট শব্দটি সেটি থেকে খুঁজে বের করতে হবে। সার্চ অ্যালগরিদম شامل টপ-টু-বটম, রাইট-টু-লেফট এবং তার বিপরীত দিক—অর্থাৎ চার দিকেই (ডায়াগোনালি বাদে)।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট- স্ট্রিং word = "LAYS"

2D String[] = { "LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS" };

আউটপুট- ২ডি ক্যারেক্টার অ্যারেতে দেওয়া স্ট্রিংর বার্তা: 7

ব্যাখ্যা - দেওয়া স্ট্রিং অ্যারেতে থেকে "LAYS" শব্দটি খুঁজে বের করতে হবে যেটি যেকোনো দিক থেকে (লেফট-টু-রাইট, রাইট-টু-লেফট, বটম-টু-টপ, টপ-টু-বটম) পাওয়া যেতে পারে। কোডের কাউন্টার ফ্ল্যাগ প্রতিবার শব্দটি পাওয়া গেলে বাড়ে এবং শেষে মোট কাউন্ট রিটার্ন করে। উদাহরণে "LAYS" ৭বার তৈরি হয়েছে:

1. LOAPYS - LAYS (বাম থেকে ডান)
2. SAYAOL - LAYS (ডান থেকে বাম)
3. LAYSST - LAYS (বাম থেকে ডান)
4. MLVAYS - LAYS (বাম থেকে ডান)
5. LAYSAA - LAYS (বাম থেকে ডান)
6. LAOYLS - LAYS (বাম থেকে ডান)
7. (নিচে থেকে উপরে) লাল রঙে LAYS

ইনপুট- স্ট্রিং word = "CAMP"

2D String[] = { "BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL" }

আউটপুট- ২ডি ক্যারেক্টার অ্যারেতে দেওয়া স্ট্রিংর বার্তা: 0

ব্যাখ্যা-: দেওয়া স্ট্রিং অ্যারেতে থেকে "LAYS" শব্দটি খুঁজে বের করতে হবে যেটি যেকোনো দিক থেকে পাওয়া যেতে পারে। উদাহরণে "BOOK" শব্দটি ০ বার তৈরি হয়েছে।

প্রোগ্রামে ব্যবহৃত পদ্ধতি

• একটি স্ট্রিং (word) এবং স্ট্রিং অ্যারে কিছু ইউটিলিটি ভেরিয়েবলের সাথে 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