मोबाइल न्यूमेरिक कीपैड समस्या

इस समस्या में, एक न्यूमेरिक मोबाइल कीपैड दिया गया है। हम केवल वर्तमान बटन के ऊपर, नीचे, दाएं और बाएं बटन दबा सकते हैं, विकर्ण कुंजियों की अनुमति नहीं है। हम कीपैड में * और # बटन भी नहीं दबा सकते।

एक अंक दिया गया है, हमें दिए गए अंकों की उन संभावित संख्याओं की संख्या ढूंढनी है जो कीपैड का उपयोग करके बनाई जा सकती हैं, दिए गए नियमों को बनाए रखते हुए।

इनपुट और आउटपुट

इनपुट: अंकों की संख्या। मान लें 3 अंकों की संख्या।
आउटपुट: दी गई शर्तों के साथ बनने वाले 3 अंकों की संख्याओं की संभावित संख्या। यहां उत्तर 138 है।

एल्गोरिदम

getCount(n)

इनपुट: अंकों की संख्या n
आउटपुट: मोबाइल कीपैड में n अंकों की संख्या टाइप करने के संभावित तरीके

शुरुआत
    यदि n <= 0, तो
        वापस 0
    यदि n = 1, तो
        वापस 10
    प्रत्येक दिशा में वर्तमान कुंजी से जाने के लिए दो ऐरे row और col परिभाषित करें
    आकार (10 x n+1) की count टेबल परिभाषित करें
    i रेंज 0 से 9 में, करें
        count[i, 0] := 0
        count[i, 1] := 1
    पूर्ण
    k रेंज 2 से n में, करें
        i रेंज 0 से 3 में, करें
            j रेंज 0 से 2 में, करें
                यदि key[i, j] ≠ * या #, तो
                    num := key[i, j]
                    count[num, k] := 0
                    सभी संभावित चालों के लिए, करें
                        rowMove := i + row[move]
                        colMove := j + col[move]
                        यदि rowMove (0..3) में, colMove (0..2) में, और key ≠ * या #, तो
                            nextNum := key[rowMove, colMove]
                            count[num, k] := count[num, k] + count[nextNum, k+1]
                    पूर्ण
                पूर्ण
            पूर्ण
        पूर्ण
    पूर्ण
    totalCount := 0
    i रेंज 1 से 9 में, करें
        totalCount := totalCount + count[i, n]
    पूर्ण
    वापस totalCount
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

char keypad[4][3] = {
    {'1','2','3'},
    {'4','5','6'},
    {'7','8','9'},
    {'*','0','#'}
};

int getCount(int n) {
    if(keypad == NULL || n <= 0)
        return 0;
    if(n == 1)
        return 10;
    
    int row[] = {0, 0, -1, 0, 1};
    int col[] = {0, -1, 0, 1, 0};
    int count[10][n+1];
    int move=0, rowMove=0, colMove=0, num = 0;
    int nextNum=0, totalCount = 0;
    
    for (int i=0; i<=9; i++) {
        count[i][0] = 0;
        count[i][1] = 1;
    }
    
    for (int k=2; k<=n; k++) {
        for (int i=0; i<4; i++) {
            for (int j=0; j<3; j++) {
                if (keypad[i][j] != '*' && keypad[i][j] != '#') {
                    num = keypad[i][j] - '0';
                    count[num][k] = 0;
                    for (move=0; move<5; move++) {
                        rowMove = i + row[move];
                        colMove = j + col[move];
                        if (rowMove >= 0 && rowMove <= 3 && colMove >=0 && colMove <= 2 &&
                            keypad[rowMove][colMove] != '*' && keypad[rowMove][colMove] != '#') {
                            nextNum = keypad[rowMove][colMove] - '0';
                            count[num][k] += count[nextNum][k-1];
                        }
                    }
                }
            }
        }
    }
    
    totalCount = 0;
    for (int i=0; i<=9; i++)
        totalCount += count[i][n];
    
    return totalCount;
}

int main() {
    int n;
    cout << "Number of digits: "; cin >> n;
    cout << "Possible Combinations: " << getCount(n);
}

आउटपुट

Number of digits: 3
Possible Combinations: 138