【数学】【深度优先搜索】【图论】【欧拉环路】753. 破解保险箱

class Solution {
public:
  string crackSafe(int n, int k) {
    if (1 == n)
    {
      for (int i = 0; i < k; i++)
      {
        m_strRet += '0' + i;
      }
      return m_strRet;
    }
    m_iK = k;
    int iMask = 1;
    for (int i = 1; i < n; i++)
    {
      iMask *= k;
    }
    vector<std::queue<int>> vNeiBo(iMask);
    for (int i = 0; i < iMask; i++)
    {
      int pre = i % (iMask / k);
      for (int j = 0; j < k; j++)
      {
        vNeiBo[i].emplace(pre * k + j);
      }
    }
    DFS(vNeiBo, 0);
    m_strRet += string(n - 2, '0'); //DFS时，已经加了一个零  
    return string(m_strRet.rbegin(),m_strRet.rend());
  }
  void DFS(vector<std::queue<int>>& vNeiBo, int cur)
  {
    while (vNeiBo[cur].size())
    {
      const auto next = vNeiBo[cur].front();
      vNeiBo[cur].pop();
      DFS(vNeiBo,next);
    }
    m_strRet += '0' + cur % m_iK;
  }
  int m_iK;
  string m_strRet;
};

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  int n ,k;
  {
    Solution sln;
    n = 2, k = 2;
    auto res = sln.crackSafe(n, k);
    Assert(strlen("01100"), res.length());
  }
  {
    Solution sln;
    n = 1, k = 2;
    auto res = sln.crackSafe(n, k);
    Assert(strlen("10"), res.length());
  }
  {
    Solution sln;
    n = 3, k = 2;
    auto res = sln.crackSafe(n, k);
    Assert(strlen("0011101000"), res.length());
  }
  {
    Solution sln;
    n = 2, k = 3;
    auto res = sln.crackSafe(n, k);
    Assert(strlen("0221120100"), res.length());
  }
}

string crackSafe(int n, int k) {
  m_iRange = pow(10, n - 1);
  m_iK = k;
  dfs(0);
  m_strRet += string(n - 1, '0');
  return m_strRet;
}