【\(hihoCoder\) \(1182\)】 欧拉路·三（\(Fleury\)算法）
一、题目描述
题目抽象
写出一个环，环上有\(2^n\)个格子，每个格子中的数字是\(0\)或\(1\)，相连着的\(n\)个格子可以组成一个数的二进制，要求给出这\(2^n\)个数字的序列，使得组成的\(2^n\)个数字全是不同的。(即从\(0\)到\(2^n-1\)）
二、解题思路
构造一个图，但是只需要考虑边，每条边假设为\(n\)个\(0/1\)组成的串，即此图有\(2^n\)条边，每边代表\(1\)个数字。
若两边经过同一个点，则可以从一条边\(k\)经过 \((k<<1)+0/1\)就是左边去掉\(1\)位，再左移一位，再在后面添加\(0\)或\(1\)，就相当于切换到另外一边。
既然可以在后面添加\(0\)或\(1\)，那么就相当于一个点有两条出边，那么也就可以看到每个点也有两条入边。边\(1001\)和\(0001\)都可以转成\(0011\)和\(0010\)。此时他们经过了\(1\)个点，前两条边为入边，后两条边为出边（如图）。
栗子
\(n = 3\); 则建\(2^{n-1}\)个点，也就是\(4\)个点，分别是 \(00，01，11，10\);
这四个点共可以连出\(8(2^3 -> 2^n)\)条边出来。
这样就转化位求欧拉路径的题了。求一条路径不重复地经过这\(8\)条边；
细节
可以从\(0\)开始出发，进行暴力\(DFS\)，需要注意的只是路径应该是欧拉路的路径，要从回溯开始计起，为了防止无限循环，要记录下访问过的路径。但是所要的答案是顺时针的，所以要从路径的前面开始输出。每次输出二进制的最后一位即可。
注：这是有向图，但是每个点都是入度=出度=\(2\)，那么可以从任意一个点出发，不仅限于\(0\)出发。（因为没有入度！=出度的点，该点是起/终点）
\(Code\) 暴力搜索\(dfs\)
#include <bits/stdc++.h>
using namespace std;
const int N = 16, M = 1 << N; // 上限32768条边,这里暴力一些，直接 1<<16,没有使用1<<15+10
int n; // n个小方框
int st[N]; // 节点是否访问过
int ans[N], al; // 欧拉路径
int k = 1; // 人为构造的一个数位全是1的二进制数，位数是2^n
void dfs(int u) {
st[u] = 1; // 该点访问过了
int x = ((u & k) << 1); // 去掉最高位再左移一位
if (!st[x]) dfs(x); // 刚左移完，后面补的是0
if (!st[++x]) dfs(x); // ++x就相当于最后一位是1
ans[++al] = u; // 路径：记录走过的边
}
int main() {
#ifndef ONLINE_JUDGE
freopen("HihoCoder1182.in", "r", stdin);
#endif
scanf("%d", &n); // n个小方框
// 2^0 ~ 2^(n-1)
// 如果是3位，那么就是2个1；如果是4位，那么就是3个1；
// 构建这么个东西，下面想去掉最前面的数字时就方便些。
// 去掉最高位时有用到
// 原来的写法
// for (int i = 2; i < n; i++) k = (k << 1) + 1;
// 黄海的写法
// 构建一个数位全是1的二进制数，去掉最高位时有用到
// 举栗子：n=3,则 1<< 3-1 <=> 1<<2=4 => 4-1=3
k = (1 << (n - 1)) - 1;
// 从数字0开始搜索
dfs(0);
// 任一合法答案
for (int i = al; i; i--) printf("%d", ans[i] & 1);
return 0;
}