इस समस्या में, हमें एक नंबर n दिया जाता है और हमें मोबाइल कीपैड बटन दबाकर सभी N अंकों के पैटर्न को प्रिंट करना होता है। बटनों को दबाते समय, हम वर्तमान बटन के केवल पास के बटन दबा सकते हैं अर्थात केवल बाएँ, दाएँ, ऊपर, नीचे कुंजियाँ ही दबाई जा सकती हैं।
आइए देखें कि पुराना कीपैड कैसा दिखता है -
| 1 | 2 एबीसी | 3 डीईएफ़ |
| 4 जीएचआई | 5 जेकेएल | 6 एमएनओ |
| 7 पीक्यूआरएस | 8 टीयूवी | 9 डब्ल्यू एक्स वाई जेड |
| * | 0 | # |
समस्या को समझने के लिए एक उदाहरण लेते हैं
Input: n=2 Output: 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 में, हम संख्या के पहले अंक के रूप में अपने कीपैड की एक-एक करके सभी कुंजियों का चयन करेंगे। अब, हम डीएफएस (जो बाएं, दाएं, ऊपर या नीचे की अनुमति देता है) का उपयोग करके संख्या के शेष अंक उत्पन्न करेंगे। की स्टोक्स)।
उदाहरण
उपरोक्त समाधान को लागू करने का कार्यक्रम -
#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