在C ++中打印由移动键盘形成的所有n位数字图案
在这个问题中，给我们一个数字n，我们必须打印所有通过按下移动键盘按钮形成的N个数字模式。在按下按钮时，我们只能按下当前按钮附近的按钮，即只能按下左，右，上，下键。
让我们看看旧键盘的样子-
ABC
DEF
GHI
JKL
MNO
PQRS
TUV
WXYZ
让我们以一个例子来了解问题
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