Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में तिजोरी तोड़ना (Cracking the Safe)


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

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

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

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

  • एक सेट visited परिभाषित करें
  • एक फंक्शन dfs() परिभाषित करें, यह s, k लेगा,
  • i := 0 से प्रारंभ करें, जब i < k, i बढ़ाते हुए, करें -
    • temp := s को i के स्ट्रिंग के साथ जोड़ें
    • यदि temp visited में नहीं है, तो -
      • temp को visited में डालें
      • temp := temp का सबस्ट्रिंग इंडेक्स 1 से अंत तक प्राप्त करें
      • dfs(temp, k)
      • ret := ret को i के स्ट्रिंग के साथ जोड़ें
  • मुख्य विधि से, निम्न करें -
  • यदि n, 1 के समान है और k, 1 के समान है, तो -
    • "0" वापस करें
  • ret := खाली स्ट्रिंग, s := खाली स्ट्रिंग
  • i := 0 से प्रारंभ करें, जब i < n - 1, i बढ़ाते हुए, करें -
    • s := s को "0" के साथ जोड़ें
  • dfs(s, k)
  • i := 0 से प्रारंभ करें, जब i < n - 1, i बढ़ाते हुए, करें -
    • ret := ret को "0" के साथ जोड़ें
  • ret वापस करें

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

उदाहरण

#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

  1. C++ में The Maze II C++ में The Maze II

    मान लीजिए एक भूलभुलैया में खाली स्थान और दीवारों के साथ एक गेंद है। अब गेंद किसी भी दिशा जैसे ऊपर, नीचे, बाएँ या दाएँ खाली पथों से गुजर सकती है, लेकिन यह तब तक लुढ़कना बंद नहीं करेगी जब तक यह दीवार से नहीं टकराती। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्थिति, गंतव्य

  1. C++ में भूलभुलैया समस्या का समाधान C++ में भूलभुलैया समस्या का समाधान

    समस्या विवरण मान लीजिए एक गेंद एक भूलभुलैया में है जिसमें खाली स्थान और दीवारें हैं। गेंद किसी भी दिशा में (ऊपर, नीचे, बाएं, दाएं) लुढ़ककर खाली रास्तों से गुजर सकती है, लेकिन यह तब तक नहीं रुकेगी जब तक यह दीवार से न टकरा जाए। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। हमें गेंद की प्रारंभिक स्

  1. भूलभुलैया III - C++ भूलभुलैया III - C++

    मान लीजिए एक भूलभुलैया है जिसमें खाली स्थान और दीवारें हैं और उस भूलभुलैया में एक गेंद भी है। गेंद ऊपर (u), नीचे (d), बाएं (l) या दाएं (r) दिशाओं में लुढ़ककर खाली स्थानों से गुजर सकती है, लेकिन यह दीवार से टकराने तक लुढ़कती रहती है। जब गेंद रुकती है, तो यह अगली दिशा चुन सकती है। उस भूलभुलैया में एक