資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究使用C++列印手機鍵盤上所有n位數字組合
在這個問題中，我們給定一個數字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
更新於：2020年1月22日
147 次瀏覽
廣告