POJ 1780 Code（欧拉回路+非递归dfs）

题意：
有个保险箱子是n位数字编码，当正确输入最后一位编码后就会打开（即输入任意多的数字只有最后n位数字有效）……要选择一个好的数字序列，最多只需按键10ⁿ+n-1次就可以打开保险箱子，即要找到一个数字序列包含所有的n位数一次且仅一次。序列要为字典序。

思路：

对于当前长度为n-1的序列，其后添加一个数字，使得添加后的序列没有在前面出现过。这样的话，以n-1位数为顶点，新增一个数后构成n位数为边，到达后n-1位数的新顶点。这样一来，就构成了一个图，我们只要不重复的经过图中所有边即可，那么这就是欧拉回路了。

在寻找路径的时候需要用dfs，但是吧，这里直接dfs是要爆栈的，所以这里必须要用非递归的方法来实现dfs，也就是要借助栈。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn = 1e5 + ;

 int n;

 int s,t,v;

 int list[maxn];

 int sta[maxn*];

 char ans[maxn*];

 void search(int v, int m)

 {

     int w;

     while(list[v]<)

     {

         int w=v*+list[v];

         list[v]++;

         sta[s++]=w;

         v=w%m;

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     while(~scanf("%d",&n) && n)

     {

         if(n==)

         {

             puts("");

             continue;

         }

         int m=pow(10.0,(double)(n-));

         for(int i=;i<m;i++)   list[i]=;  //list【i】记录了i顶点接下来要走的边，因为是要按字典序顺序，

                                            //所以它肯定先走添加0的，然后1，2...直到9

         s=,t=,v=;

         search(v,m);  //从起点出发会有10条边可走，先从起点出发随便走一条，当然也不是随便的...先走一下字典序小的那条路

         while(s)  //有些顶点可能还有别的路可以走，所以继续选择顶点把该顶点剩余的未走的边走完

         {

             v=sta[--s]; ans[t++]=v%+'';

             v/=;

             search(v,m);

         }

         for(int i=;i<n;i++)   printf("");

         while(t)  printf("%c",ans[--t]);

         printf("\n");

     }

     return ;

 }

秒客网

POJ 1780 Code（欧拉回路+非递归dfs）

相关文章