C++ এ সেফ ক্র্যাক করা

ধরুন আমাদের একটি বাক্স আছে যা একটি পাসওয়ার্ড দ্বারা সুরক্ষিত। পাসওয়ার্ড হল n সংখ্যার একটি ক্রম যেখানে প্রতিটি সংখ্যা প্রথম k ডিজিটের একটি হতে পারে 0, 1, ..., k-1। সুতরাং, যখন আমরা একটি পাসওয়ার্ড রাখি, তখন প্রবেশ করা শেষ n সংখ্যাগুলি স্বয়ংক্রিয়ভাবে সঠিক পাসওয়ার্ডের সাথে মিলিত হবে৷

সুতরাং উদাহরণস্বরূপ, সঠিক পাসওয়ার্ডটি "563" ধরে নিলে, যদি আমরা "285639" রাখি, তাহলে বক্সটি খুলবে কারণ সঠিক পাসওয়ার্ডটি প্রবেশ করা পাসওয়ার্ডের প্রত্যয়ের সাথে মেলে। আমাদের ন্যূনতম দৈর্ঘ্যের যেকোন পাসওয়ার্ড খুঁজে বের করতে হবে যা এটি প্রবেশ করার সময় বাক্সটি খোলার গ্যারান্টিযুক্ত৷

যখন ইনপুট n =2 এবং k =2 এর মত হয়, তখন ফলাফল হতে পারে “01100”, “00110”, “10011”, “11001”, তাদের যেকোনো একটি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ভিজিটেড বলে একটি সেট সংজ্ঞায়িত করুন
• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এতে s, k,
লাগবে
• আরম্ভ করার জন্য i :=0, যখন i করুন
• temp :=s concatenate i as string
• যদি temp পরিদর্শনে না থাকে, তাহলে −
  • ভিজিটেড টেম্প ইনসার্ট করুন
  • temp :=সূচক 1 থেকে শেষ পর্যন্ত তাপমাত্রার সাবস্ট্রিং পান
  • dfs(temp, k)
  • ret :=ret concatenate 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