数据结构
网络
关系数据库管理系统(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 次浏览
广告