C++-এ মোবাইল কিপ্যাড থেকে n-অঙ্কের সব প্যাটার্ন প্রিন্ট করা

এই সমস্যায় একটি সংখ্যা n দেওয়া আছে। আমাদের মোবাইল কিপ্যাডের বাটন চাপা দিয়ে তৈরি n-অঙ্কের সব প্যাটার্ন প্রিন্ট করতে হবে। বাটন চাপার সময় শুধু বর্তমান বাটনের নিকটবর্তী বাটনগুলো (বাম, ডান, উপর, নিচ) চাপা যাবে।

পুরানো কিপ্যাডের লেআউট

উদাহরণ

ইনপুট: n=2
আউটপুট: 12 14 21 23 25 32 36 41 45 47 52 54 56 58 63 65 69 74 78 85 87 89 80 96 98

এই সমস্যাটি সমাধানের জন্য ডেপথ-ফার্স্ট সার্চ (DFS) ব্যবহার করা হবে। DFS-এ একেEfter একে কিপ্যাডের সব কীকে সংখ্যার প্রথম অঙ্ক হিসেবে নির্বাচন করা হবে। এখন DFS ব্যবহার করে বাকি অঙ্কগুলো তৈরি করা হবে (যা বাম, ডান, উপর বা নিচ কী স্ট্রোকের অনুমতি দেয়)।

বাস্তবায়ন

#include <bits/stdc++.h> 
using namespace std; 

bool isSafe(int x, int y, bool Visited[][3]) { 
    return (x >= 0 && x < 4 && y >= 0 && y < 3 && !Visited[x][y]); 
} 

void searchNumber(bool visited[][3], int Keypad[][3], int n, string pattern, int x, int y) { 
    pattern.push_back((Keypad[x][y] + '0')); 
    if (pattern.size() == n) { 
        cout << pattern << "\t"; 
        return; 
    } 
    static int row[] = { 0, 1, 0, -1 }; 
    static int col[] = { 1, 0, -1, 0 }; 
    visited[x][y] = true; 
    for (int k = 0; k < 4; k++) 
        if (isSafe(x + row[k], y + col[k], visited) && Keypad[x + row[k]][y + col[k]] != -1) 
            searchNumber(visited, Keypad, n, pattern, x + row[k], y + col[k]); 
    visited[x][y] = false; 
    pattern.pop_back(); 
} 

void GenerateNDigitNumber(int Keypad[][3], int n) { 
    bool visited[4][3]; 
    memset(visited, false, sizeof(visited)); 
    for (int i = 0; i < 4; i++) 
        for (int j = 0; j < 3; j++) 
            if (Keypad[i][j] != -1) 
                searchNumber(visited, Keypad, n, "", i, j); 
} 

int main() { 
    int Keypad[4][3] = { 
        { 1, 2, 3 }, 
        { 4, 5, 6 }, 
        { 7, 8, 9 }, 
        { -1, 0, -1 } 
    }; 
    int n = 2; 
    cout << "All " << n << " digit number generated from keypad are :\n"; 
    GenerateNDigitNumber(Keypad, n); 
    return 0; 
}

আউটপুট

All 2 digit number generated from keypad are :
12 14 23 25 21 36 32 45 47 41 56 58 54 52 69 65 63 78 74 89 80 87 85 98 96 08