C++에서 모바일 키패드로 형성된 모든 n자리 패턴 인쇄

이 문제에서 숫자 n이 주어지고 모바일 키패드 버튼을 눌러 형성된 N자리 패턴을 모두 인쇄해야 합니다. 버튼을 누르는 동안 현재 버튼의 근처 버튼만 누를 수 있습니다. 즉, 왼쪽, 오른쪽, 위, 아래 키만 누를 수 있습니다.

기존 키패드가 어떻게 생겼는지 봅시다 -

문제를 이해하기 위해 예를 들어보겠습니다.

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