แคร็กตู้เซฟใน C ++

สมมติว่าเรามีกล่องที่ป้องกันด้วยรหัสผ่าน รหัสผ่านคือลำดับของ n หลัก โดยที่แต่ละหลักสามารถเป็นหนึ่งใน k หลักแรก 0, 1, ..., k-1 ดังนั้นเมื่อเราใส่รหัสผ่าน n หลักสุดท้ายที่ป้อนจะถูกจับคู่กับรหัสผ่านที่ถูกต้องโดยอัตโนมัติ

ตัวอย่างเช่น สมมติว่ารหัสผ่านที่ถูกต้องคือ "563" หากเราใส่ "285639" กล่องจะเปิดขึ้นเนื่องจากรหัสผ่านที่ถูกต้องตรงกับส่วนต่อท้ายของรหัสผ่านที่ป้อน เราต้องหารหัสผ่านที่มีความยาวขั้นต่ำที่รับประกันว่าจะเปิดกล่องได้เมื่อถึงจุดหนึ่งที่ป้อน

เมื่ออินพุตเป็น n =2 และ k =2 ผลลัพธ์อาจเป็น “01100”, “00110”, “10011”, “11001” หรืออย่างใดอย่างหนึ่ง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดชุดหนึ่งเรียกว่าเยี่ยมชมแล้ว
• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้เวลา s, k,
• สำหรับการเริ่มต้น i :=0 เมื่อฉัน
• temp :=s concatenate i as string
• ถ้าอุณหภูมิไม่เข้า −
  • ใส่อุณหภูมิในการเข้าชม
  • temp :=รับสตริงย่อยของ temp จากดัชนี 1 ถึงจุดสิ้นสุด
  • dfs(ชั่วคราว, k)
  • ret :=ret เชื่อม i เป็นสตริง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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);
         }
      }
   }
};
main(){
   Solution ob;
   cout << (ob.crackSafe(2,2));
}

อินพุต

2
2

ผลลัพธ์

01100