พิมพ์รูปแบบตัวเลข n ทั้งหมดที่เกิดจากปุ่มกดมือถือใน C++

ในปัญหานี้ เราจะได้รับหมายเลข 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