[UVA] 10506 - Ouroboros

題目連結

題意：

給你M, N兩個數字，
M是表示一組幾個數字，
N是代表N進位，最大到10進位
現在要利用N進位的數字去做排列組合，可以排出N的M次方種組合，
例如M = 2，N = 3，可以排出3的2次方 = 9種，
也就是
(00)
(01)
(02)
(10)
(11)
(12)
(20)
(21)
(22)

今天有一字串可以在這字串中找到所有這些組合的數字，
最後一組要連接第一組。

以上面M = 2，N = 3為例，=> 字串可以為 001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
001021122
9組數字都可以在字串中找到，
題目要你輸出這個字串(可能很多答案，隨便一個都可以)

--------------------------------------------------

我的作法：

如果要枚舉所有字串的可能再去判斷字串中是否存在所有數字組，

字串最長長度為65536，最大到10進位，

要做出所有字串有10的65536次方種，

然後每個字串要去搜尋65536個數字組，

超級無敵多，一定超時。

可以換個想法，

每一組數字都要出現，
而且只出現一次，
可以將每一組數字當作一個node，
對每個node去連接其他可以與其相連的node，例如(01)可以連(10), (11), (12)..
那題目要求的就是一條尤拉迴路(euler circuit)！

--------------------------------------------------

程式碼：

/* 題目: UVa 10506 - Ouroboros

 * Language: C++

 * Created on: 2015年12月10日

 *   Author: hanting

 */

#include <iostream>

#include <vector>

#include <cmath>

#include <map>

using namespace std;

vector<vector<int> > adjList;

vector<int> visit;

vector<string> node;

map<string, int> store; // <node, nodeID>

vector<int> eulerCircuit;

int allPermutation;

void init(int n)

{

     adjList.assign(n, vector<int>());

     visit.assign(n, 0);

     node.clear();

     store.clear();

     eulerCircuit.clear();

}

void buildNode(int digit, int base)

{

     string str(digit, '0');

     node.push_back(str);

     store[str] = 0;

     for (int i = 0; i < allPermutation - 1; i++)

     {

           str[str.size() - 1]++; // "000" -> "001"

           for (int j = str.size() - 1; j > 0; j--) // base = 2, "002" -> "010"

           {

                if (str[j] >= base + '0')

                {

                     str[j] = '0';

                     str[j - 1]++;

                }

           }

           node.push_back(str);

           store[str] = node.size() - 1;

     }

}

void LinkNode(int a, int b)

{

    if(a != b)

        adjList[a].push_back(b);

}

void Link(int n, int base) // base = 3, (000) link (001), (002)

{

     string tmp = node[n].substr(1);

     tmp += " ";

     for (int i = '0'; i < '0' + base; i++)

     {

           tmp[tmp.size() - 1] = i;

           LinkNode(n, store[tmp]);

     }

}

void DFS(int cur, bool &finish)

{

     visit[cur] = 1;

     eulerCircuit.push_back(cur);

     if (eulerCircuit.size() == node.size())

     {

         string last, first;

         last = node[cur];

         first = node[0];

           if (last.substr(1) == first.substr(0, first.size() - 1))

           {// the last node link the first node

                finish = true;

           }

           return;

     }

     for (int i = 0; i < (int) adjList[cur].size(); i++)

     {

           int tmp = adjList[cur][i];

           if (!visit[tmp])

           {

                DFS(tmp, finish);

                if(finish) return ;

           }

     }

     visit[cur] = 0;

     eulerCircuit.pop_back();

}

int main()

{

     int M, N;

     while (cin >> M >> N)

     {

           allPermutation = pow(N, M);

           init(allPermutation);

           buildNode(M, N);

           for (int i = 0; i < (int) node.size(); i++)

           {

                Link(i, N);

           }

           bool finish = false;

           DFS(0, finish);

           for (int i = 0; i < (int) eulerCircuit.size(); i++)

           {

                int t = eulerCircuit[i];

                cout << node[t][0];

           }

           cout << endl;

     }

     return 0;

}