雙向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 }