C++で金庫を割る

パスワードで保護されているボックスがあるとします。パスワードはn桁のシーケンスであり、各桁は最初のk桁の0、1、...、k-1のいずれかになります。そのため、パスワードを入力するときに、入力された最後のn桁が自動的に正しいパスワードと照合されます。

したがって、たとえば、正しいパスワードが「563」であると仮定して、「285639」を入力すると、正しいパスワードが入力されたパスワードのサフィックスと一致するため、ボックスが開きます。入力した時点でボックスを開くことが保証されている最小の長さのパスワードを見つける必要があります。

入力がn=2およびk=2の場合、結果は「01100」、「00110」、「10011」、「11001」のいずれかになります。

これを解決するには、次の手順に従います-

• visitedと呼ばれる1つのセットを定義します
• 関数dfs（）を定義します。これには、s、k、
が必要です。
• iを初期化する場合：=0、i
• temp：=sはiを文字列として連結します
• 臨時雇用者が訪問していない場合、-
  • 訪問者に臨時雇用者を挿入
  • temp：=インデックス1から終了までのtempのサブストリングを取得します
  • dfs（temp、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