用本班数学神牛高瑞阳的话说“这是一道水题”。原题是数学题，要求求解n=3时的最小步数。
据说高同学用五分钟AC原题，并证明：有且仅有一种方案解决这个问题。
而本题作为usaco上的一道题目，必要的数学功底自然是必要的，但我们也应以OIer的思维方式来解决次题。
主体是搜索，加上状态压缩的DFS。（用show来调试，逐步写成4个操作，非常顺利。）
由于有且仅有一种方案解决这个问题，那么大量的可行性剪枝是可以显然得到的。
显然，w向右移动之后，再向左移是不符合最优性原理的，所以我们只考虑w右移。同理，只考虑b的左移。
（高神牛的那个结论可以说明，只要不是最优性的操作，必然是不可行的操作）
此时的搜索数已经很小了，每个节点的分支数<2,基本上可以可以合理的通过此题。
（根据我的推测时间复杂度O（2^(2*n)））
又因为，有且仅有一种方案解决这个问题，所以我们输出时不用考虑答案的顺序。只要注意换行就行了。
代码
/*
USER:zyn19961
LANG:C++
TASK:shuttle
*/
#include<cstdio>
#include<cstring>
int n;
bool flag=false;
int use[100001];
int goal=0;
void show(int m,int t);
void work(int i,int place,int m);
int main(){
freopen("shuttle.in","r",stdin);
freopen("shuttle.out","w",stdout);
int mm=0;
scanf("%d",&n);
goal=1<<n;goal--;goal<<=(n+1);
work(1,n+1,(1<<n)-1);
fclose(stdin);
fclose(stdout);
return 0;
}
void work(int i,int place,int m){
int t;
//show(m,place);
if(flag)return ;
if(m==goal){
flag=true;
for(int j=1;j<=i-2;j++){
if(j%20==0)
printf("%d\n",use[j]);
else
printf("%d ",use[j]);
}
printf("%d\n",use[i-1]);
return;
}
if(m&(1<<(place-2))&&place>=2){
use[i]=place-1;
t=m-(1<<(place-2));
t+=(1<<(place-1));
work(i+1,place-1,t);
}
if(!(m&(1<<(place)))&&place<=n*2){
use[i]=place+1;
work(i+1,place+1,m);
}
if((m&(1<<(place)))&&(!(m&(1<<(place+1))))&&place<=2*n-1){
use[i]=place+2;
work(i+1,place+2,m);
}
if((m&(1<<place-3))&&(!(m&(1<<(place-2))))&&place>=3){
use[i]=place-2;
t=m-(1<<(place-3));
t+=1<<(place-1);
work(i+1,place-2,t);
}
}
void show(int m,int t){
for(int i=0;i<=t-2;i++)
printf("%d",(m&(1<<i))>>i);
printf("*");
for(int i=t;i<=n*2;i++)
printf("%d",(m&(1<<i))>>i);
printf("\n");
}关于那个非常非常重要的结论，其实我也想到了，如果想要证明的话，去找高神牛吧！
感谢二中温暖的办公室和无线网络。
12.12 by zyn