C++ में तिजोरी को क्रैक करना

मान लीजिए हमारे पास एक बॉक्स है जो पासवर्ड से सुरक्षित है। पासवर्ड n अंकों का एक क्रम है जहां प्रत्येक अंक पहले k अंक 0, 1, ..., k-1 में से एक हो सकता है। इसलिए, जब हम कोई पासवर्ड डाल रहे होते हैं, तो दर्ज किए गए अंतिम n अंक स्वचालित रूप से सही पासवर्ड से मेल खाते हैं।

इसलिए उदाहरण के लिए, सही पासवर्ड "563" मानते हुए, यदि हम "285639" डालते हैं, तो बॉक्स खुल जाएगा क्योंकि सही पासवर्ड दर्ज किए गए पासवर्ड के प्रत्यय से मेल खाता है। हमें न्यूनतम लंबाई का कोई भी पासवर्ड खोजना होगा जो इसे दर्ज करने के किसी बिंदु पर बॉक्स को खोलने की गारंटी है।

जब इनपुट n =2 और k =2 जैसा हो, तो परिणाम "01100", "00110", "10011", "11001", इनमें से कोई भी हो सकता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• विज़िट नामक एक सेट को परिभाषित करें
• एक फ़ंक्शन dfs() परिभाषित करें, इसमें s, k,
लगेगा
• इनिशियलाइज़ i :=0 के लिए, जब i करें
• अस्थायी:=s मैं स्ट्रिंग के रूप में संयोजित करता हूं
• अगर टेम्परेचर नहीं आया है, तो −
  • भेजे गए में अस्थायी डालें
  • अस्थायी:=सूचकांक 1 से अंत तक अस्थायी की सबस्ट्रिंग प्राप्त करें
  • dfs(temp, k)
  • ret :=ret concatenate i as string

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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