इस समस्या में, हमें एक संख्या n दी गई है और हमें मोबाइल कीपैड बटन दबाकर बने सभी N अंकों के पैटर्न प्रिंट करने हैं। बटन दबाते समय, हम केवल वर्तमान बटन के आस-पास के बटन दबा सकते हैं यानी केवल बाएं, दाएं, ऊपर, नीचे के कुंजियों को दबाया जा सकता है।
पुराना कीपैड
| 1 | 2 ABC |
3 DEF |
| 4 GHI |
5 JKL |
6 MNO |
| 7 PQRS |
8 TUV |
9 WXYZ |
| * | 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 में, हम अपने कीपैड के सभी कुंजियों को एक-एक करके संख्या के पहले अंक के रूप में चुनेंगे। अब, हम 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