用C ++破解保险箱

假设我们有一个受密码保护的盒子。密码是n位数字的序列，其中每个数字可以是前k个数字0、1，...，k-1中的一个。因此，当我们输入密码时，最后输入的n位数字将自动与正确的密码匹配。

因此，例如，假设正确的密码是“ 563”，那么如果我们输入“ 285639”，则该框将打开，因为正确的密码与输入密码的后缀匹配。我们必须找到可以保证在输入框时打开框的最小长度的任何密码。

当输入类似n = 2和k = 2时，结果可以是“ 01100”，“ 00110”，“ 10011”，“ 11001”中的任何一个。

为了解决这个问题，我们将遵循以下步骤-

• 定义一组称为访问的

• 定义一个函数dfs()，它将取s，k，

• 对于初始化i：= 0，当i <k时，更新（将i增加1），执行-

• 将temp插入访问

• temp：=从索引1到结尾获取temp的子字符串

• dfs（温度，k）

• ret：= ret将我连接为字符串

• temp：= s将我连接为字符串

• 如果没有访问temp，则-

• 从主要方法中，执行以下操作-

• 如果n与1相同且k与1相同，则-

• 返回“ 0”

• ret：=空字符串，s：=空字符串

• 对于初始化i：= 0，当i <n-1，更新（将i增加1）时，执行-

• s：= s连接“ 0”

• dfs(s,k)

• 对于初始化i：= 0，当i <n-1，更新（将i增加1）时，执行-

• 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