雪竹的天空

theorix

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  34 随笔 :: 0 文章 :: 20 评论 :: 0 Trackbacks
双向BFS
  1 #include<iostream>
  2 #include<map>
  3 #include<set>
  4 #include<vector>
  5 #include<deque>
  6 using namespace std;
  7 inline int adj(int n)
  8 {
  9     int dmin=n,i;
 10     int tmp=(1<<13);
 11     for(i=1;i<13;i++)
 12     {
 13         n<<=1;
 14         if(n&tmp)
 15         {
 16             n-=tmp;
 17             n|=1;
 18         }
 19         if(dmin>n)
 20             dmin=n;
 21     }
 22     return dmin;
 23 }
 24 inline int change(int n,int a,int b)
 25 {//cout<<a<<" "<<b<<" ";
 26     int i;
 27     for(i=0;i<3;i++)
 28     {
 29         if(a==13)a=0;
 30         if(b==26)b=13;
 31         int t1=(n>>a)&1;
 32         int t2=(n>>b)&1;
 33         if(t1!=t2)
 34         {
 35             if(t1==1)
 36             {
 37                 n-=(1<<a);
 38                 n+=(1<<b);
 39             }
 40             else
 41             {
 42                 n+=(1<<a);
 43                 n-=(1<<b);
 44             }
 45         }
 46         a++;
 47         b++;
 48     }
 49     int ans=0;
 50     ans|=adj(n>>13)<<13;
 51     ans|=adj(n&((1<<13)-1));
 52     return ans;
 53 }
 54 int main()
 55 {
 56     int i,j,k;
 57     int start=0xE3FF;
 58     vector<int>a;
 59     map<int,int >Smap;
 60     Smap[start]=1;
 61     Smap[(1<<13)-1]=0;
 62     int tmp;
 63     for(i=0;i<13;i++)
 64         for(j=13;j<26;j++)
 65         {
 66             tmp=change(start,i,j);
 67             a.push_back(tmp);
 68             if(Smap.find(tmp)==Smap.end())
 69                 Smap[tmp]=2;
 70         }
 71     for(k=0;k<a.size();k++)
 72         for(i=0;i<13;i++)
 73             for(j=13;j<26;j++)
 74             {
 75                 tmp=change(a[k],i,j);
 76                 if(Smap.find(tmp)==Smap.end())
 77                 {
 78                     Smap[tmp]=3;
 79                 }
 80             }
 81     char ch[30];
 82     while(gets(ch)>0)
 83     {
 84         start=0;
 85         for(i=0;i<26;i++)
 86         {
 87             if(ch[i]=='y')
 88                 start|=1;
 89             start<<=1;
 90         }
 91         start>>=1;
 92         int tt=start;
 93         start=0;
 94         start|=adj(tt&((1<<13)-1));
 95         start|=(adj(tt>>13))<<13;//cout<<start<<"--------"<<tt<<endl;
 96         deque<int>q;
 97         set<int>Iset;
 98         q.push_back(start);
 99         q.push_back(0);
100         int ans=-1;
101         if(Smap.find(start)!=Smap.end())
102             {
103                 ans=Smap[start];
104                 goto out;
105             }
106         while(!q.empty())
107         {
108             int now=q.front();
109             q.pop_front();
110             int cost=q.front();
111             q.pop_front();
112             for(i=0;i<13;i++)
113                 for(j=13;j<26;j++)
114                 {
115                     tmp=change(now,i,j);
116                     if(Smap.find(tmp)!=Smap.end())
117                     {
118                         ans=cost+Smap[tmp]+1;
119                         goto out;
120                     }
121                     if(Iset.find(tmp)==Iset.end())
122                     {
123                         Iset.insert(tmp);
124                         q.push_back(tmp);
125                         q.push_back(cost+1);
126                     }
127                 }
128         }
129         out:
130         printf("%d\n",ans);
131     }
132 }

posted on 2008-08-29 23:09 雪竹的天空( theorix ) 阅读(405) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理