พิมพ์รูปแบบตัวเลข N หลักจาก Keypad โทรศัพท์ใน C++

ภาพรวมปัญหา

ได้รับ n ต้องพิมพ์รูปแบบตัวเลข N หลักจาก Keypad โทรศัพท์เก่า กดได้เฉพาะปุ่มติดกัน (ซ้าย, ขวา, บน, ล่าง)

Keypad Layout

ตัวอย่าง

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)

1. ลองทุกปุ่มเป็นหลักแรก
2. DFS ขยายตัวเลขโดยเคลื่อนที่ซ้าย/ขวา/บน/ล่าง
3. ใช้ Visited array ป้องกันซ้ำในเส้นทางเดียว

ตัวอย่างโค้ด C++

#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;
}

ผลลัพธ์ (Output)

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