<p>There is a safe protected by a password. The password is a sequence of <code>n</code> digits where each digit can be in the range <code>[0, k - 1]</code>.</p>

<p>The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the <strong>most recent </strong><code>n</code><strong> digits</strong> that were entered each time you type a digit.</p>

<ul>
	<li>For example, the correct password is <code>&quot;345&quot;</code> and you enter in <code>&quot;012345&quot;</code>:

	<ul>
		<li>After typing <code>0</code>, the most recent <code>3</code> digits is <code>&quot;0&quot;</code>, which is incorrect.</li>
		<li>After typing <code>1</code>, the most recent <code>3</code> digits is <code>&quot;01&quot;</code>, which is incorrect.</li>
		<li>After typing <code>2</code>, the most recent <code>3</code> digits is <code>&quot;012&quot;</code>, which is incorrect.</li>
		<li>After typing <code>3</code>, the most recent <code>3</code> digits is <code>&quot;123&quot;</code>, which is incorrect.</li>
		<li>After typing <code>4</code>, the most recent <code>3</code> digits is <code>&quot;234&quot;</code>, which is incorrect.</li>
		<li>After typing <code>5</code>, the most recent <code>3</code> digits is <code>&quot;345&quot;</code>, which is correct and the safe unlocks.</li>
	</ul>
	</li>
</ul>

<p>Return <em>any string of <strong>minimum length</strong> that will unlock the safe <strong>at some point</strong> of entering it</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1, k = 2
<strong>Output:</strong> &quot;10&quot;
<strong>Explanation:</strong> The password is a single digit, so enter each digit. &quot;01&quot; would also unlock the safe.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, k = 2
<strong>Output:</strong> &quot;01100&quot;
<strong>Explanation:</strong> For each possible password:
- &quot;00&quot; is typed in starting from the 4<sup>th</sup> digit.
- &quot;01&quot; is typed in starting from the 1<sup>st</sup> digit.
- &quot;10&quot; is typed in starting from the 3<sup>rd</sup> digit.
- &quot;11&quot; is typed in starting from the 2<sup>nd</sup> digit.
Thus &quot;01100&quot; will unlock the safe. &quot;10011&quot;, and &quot;11001&quot; would also unlock the safe.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 4</code></li>
	<li><code>1 &lt;= k &lt;= 10</code></li>
	<li><code>1 &lt;= k<sup>n</sup> &lt;= 4096</code></li>
</ul>

class Solution {

    template<typename T>
    class Array2D {
        T* data;
        size_t N, M;
    public:
        Array2D(size_t n, size_t m) : N(n), M(m) { data = new T[N * M]; }
        ~Array2D() { delete[] data; }
        inline T* operator[](size_t i) { return &data[i * M]; }
        inline T& operator()(size_t i, size_t j) { return data[i * M + j]; }
        void dump(){
            for (int i = 0; i < N; i++){
                cout << i << ": ";
                for (int j = 0; j < M; j++){
                    cout << "[" << j << "]=" << (*this)(i, j) << " ";
                }
                cout << endl;
            }
        }
    };

    string format_base_k(int x, int n, int k){
        string s(n, 'X');
        for (int i = 1; i <= n; i++){
            s[n - i] = '0' + (x % k);
            x /= k;
        }
        return s;
    }

    bool DFS(int i, Array2D<bool>& e, vector<bool>& f, int n, int m, vector<int>& s){
        s[m] = i;
        m++;
        if (m == n){
            return true;
        }
        f[i] = true;
        for (int j = 0; j < n; j++){
            if (e(i, j) && !f[j]){
                if (DFS(j, e, f, n, m, s)){
                    return true;
                }
            }
        }
        f[i] = false;
        return false;
    }

public:
    string crackSafe(int n, int k) {
        //n = 2;
        //k = 3;

        const int V = pow(k, n);
        Array2D<bool> e(V, V);

        for (int i = 0; i < V; i++){
            for (int j = 0; j < V; j++){
                e(i, j) = false;
            }
        }

        if (n > 1){
            for (int i = 0, m = pow(k, n-1); i < V; i++){
                for (int j = 0; j < V; j++){
                    if (i != j){
                        e(i, j) = (i % m) == (j / k);
                        /*
                        if (e(i, j)){
                            cout << format_base_k(i, n, k) << ":" << i << "->" << format_base_k(j, n, k) << ":" << j << endl;
                        }*/
                    }
                }
            }
        }
        else {
            string passwd = "0";
            for (int i = 1; i < k; i++){
                passwd.push_back('0' + i);
            }
            return passwd;
        }

        vector<bool> f(V, false);
        vector<int> s(V, -1);
        DFS(0, e, f, V, 0, s);
        string passwd = format_base_k(s[0], n, k);
        for (int i = 1; i < V; i++){
            passwd.push_back('0' + s[i]%k);
        }
        return passwd;
    }
};
26100