Euroboros Snake

タイトルリンク:
http://poj.org/problem?id=1392
タイトル:
nをあげて、2^nの0、1列を見つけて、サイクルごとに1つ移動させて、異なる数を表します.全部で0--2^n-1の各数を表すことができます.
問題解決の考え方:
0-2^(n-1)-1を番号として1本の木を作り、2^(n-1)個のノードを作り、あるノードの後ろに0または1を追加し、最上位を削除すると、次のノードが得られ、2つのノードの間に1本のエッジがつながっている.
図中の各エッジは1つの数を表し、2^nの数があり、それぞれ異なる.
タイトルはディクショナリシーケンスが最小であることを要求し,2^(n−1−1ノードから始まり,各ノードに0のエッジを先に加算し,後に1のエッジを加算することで,最終的なディクショナリシーケンスが最小であることを保証する.
コード:
 

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF (1<<30)

#define PI acos(-1.0)

using namespace std;



struct Inf  //     ，        ，v    ，via   0  1，vis        

{

   int v,via;

   bool vis;

};



vector<Inf>myv[17000]; //2^14=16384

char path[33000]; //     2^n  ，2^15=32768

int n,cnt;



void init() //       

{

   for(int i=0;i<=n;i++)

      myv[i].clear();

   return ;

}



void dfs(int cur)

{

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

   {

      if(myv[cur][i].vis==false)

      {

         myv[cur][i].vis=true;

         dfs(myv[cur][i].v);

         path[++cnt]=myv[cur][i].via+'0';//   ，          ，    

      }

   }

   return ;

}



int main()

{

   int k;



   while(scanf("%d%d",&n,&k)!=EOF)

   {

      if(n+k==0)

         break;

      int lan=n;

      n=(1<<(n-1))-1; //       

      init();



      struct Inf temp;

      for(int i=0;i<=n;i++)

      {

         int tt=(i<<1)-((i&(1<<(lan-2)))<<1);//    0      

         //printf("i:%d  %d
",i,tt);

         temp.v=tt;

         temp.via=0;

         temp.vis=false;



         myv[i].push_back(temp);



         tt+=1; //    1      

         temp.v=tt;

         temp.via=1;

         myv[i].push_back(temp);

      }

      cnt=-1;

      dfs(n);

      path[++cnt]='\0';

      std:reverse(path,path+cnt);//   

      //printf("%s
",path);

      int ans=0;

      for(int i=k,j=1;j<=lan;j++,i++) //    k        ，   n 

         ans=(ans<<1)+path[i%cnt]-'0';

      printf("%d
",ans);

   }

   return 0;

}