แตกปลอดกล่อง (Cracking the Safe) ใน C++

ภาพรวมปัญหา

สมมติว่ามีกล่องที่ป้องกันด้วยรหัสผ่าน รหัสผ่านคือลำดับ n หลัก แต่ละหลักเป็น 0 ถึง k-1 เมื่อป้อนรหัส หลัง n หลักสุดท้ายจะถูกตรวจสอบกับรหัสที่ถูกต้อง ตัวอย่าง: รหัส "563" ป้อน "285639" กล่องจะเปิด เพราะ "563" ตรงกับ suffix หารหัสผ่านสั้นที่สุดที่รับประกันว่าจะเปิดกล่องได้ในบางจุด

ตัวอย่าง

n = 2, k = 2 → ผลลัพธ์อาจเป็น "01100", "00110", "10011", "11001" (De Bruijn sequence)

แนวทางแก้ปัญหา (Hierholzer's Algorithm / DFS)

• ปัญหานี้เทียบเท่ากับการหา Eulerian cycle ใน De Bruijn graph
• ใช้ DFS สร้างลำดับ: จากโหนด s (ความยาว n-1) ลองต่อทุกตัวอักษร 0..k-1
• ถ้า edge (s + c) ยังไม่ได้ใช้ ให้ mark ใช้ แล้ว DFS ต่อจาก suffix ของ s+c
• Backtracking: เพิ่ม c เข้าผลลัพธ์หลัง DFS
• เติม n-1 ตัว '0' ทั้งหน้าและท้าย

ตัวอย่างโปรแกรม

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    set<string> visited;
    string ret;
    
    string crackSafe(int n, int k) {
        if(n == 1 && k == 1) return "0";
        ret = "";
        string s = "";
        for(int i = 0; i < n - 1; i++) s += "0";
        dfs(s, k);
        for(int i = 0; i < n - 1; i++) ret += "0";
        return ret;
    }
    
    void dfs(string s, int k) {
        string temp;
        for(int i = 0; i < k; i++) {
            temp = s + to_string(i);
            if(!visited.count(temp)) {
                visited.insert(temp);
                temp = temp.substr(1);
                dfs(temp, k);
                ret += to_string(i);
            }
        }
    }
};

int main() {
    Solution ob;
    cout << (ob.crackSafe(2, 2));
}

Input

2 2

Output

01100