সি++-এ সেফ ফাটানো (Cracking the Safe)

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

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

যখন n = 2 এবং k = 2, ফলাফল হতে পারে "01100", "00110", "10011", "11001" - যেকোনো একটি।

সমাধানের ধাপসমূহ

• একটি visited সেট সংজ্ঞায়িত করুন
• dfs() ফাংশন সংজ্ঞায়িত করুন যা s, k নিবে
  • i := 0 থেকে k-1 পর্যন্ত
    • temp := s + to_string(i)
    • যদি temp visited-এ নেই
      • temp কে visited-এ যোগ করুন
      • temp := temp.substr(1)
      • dfs(temp, k)
      • ret := ret + to_string(i)
• মূল ফাংশন থেকে:
  • যদি n==1 && k==1 হয়, "0" রিটার্ন করুন
  • ret := "", s := ""
  • i := 0 থেকে n-2 পর্যন্ত: s += "0"
  • dfs(s, k)
  • i := 0 থেকে n-2 পর্যন্ত: 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