要将W...W_B...B变成B...B_W...W，每次可以1、交换空格和相邻格；2、你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。用最少步数，打印出每次移动的棋子（最小的一组解）

直接dfs，要优化。很明显W向右，B向左，每一步有4种情况：1.WB_->_BW;2.W_->_W;3._B->B_;4._WB->BW_。要按照这个顺序判断，这样就直接是最小的一组解了。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define inf 2147483647
#define mp make_pair
#define pii pair<int,int>
#define pb push_back
using namespace std;inline int read(){int x=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x;
}int n,b[30];
bool f;
stack<int> s;inline void dfs(int a[],int p){f=1;for(int i=1;i<=n;++i) if(a[i]!=0){f=0;break;}if(a[n+1]==2){for(int i=n+2;i<=2*n+1;++i) if(a[i]!=1){f=0;break;}if(f){s.push(p);return;}}if(p>2&&a[p-2]==1&&a[p-1]==0){swap(a[p],a[p-2]);dfs(a,p-2);if(f){s.push(p);return;}swap(a[p],a[p-2]);}if(p>1&&a[p-1]==1){swap(a[p],a[p-1]);dfs(a,p-1);if(f){s.push(p);return;}swap(a[p],a[p-1]);}if(p<=2*n&&a[p+1]==0){swap(a[p],a[p+1]);dfs(a,p+1);if(f){s.push(p);return;}swap(a[p],a[p+1]);}if(p<2*n&&a[p+2]==0&&a[p+1]==1){swap(a[p],a[p+2]);dfs(a,p+2);if(f){s.push(p);return;}swap(a[p],a[p+2]);}
}int main()
{freopen("shuttle.in","r",stdin);freopen("shuttle.out","w",stdout);n=read();for(int i=1;i<=n;++i) b[i]=1;b[n+1]=2;dfs(b,n+1);int tot=1;s.pop();printf("%d",s.top());s.pop();while(!s.empty()){++tot;if(tot%20!=1) printf(" ");printf("%d",s.top()),s.pop();if(tot%20==0) puts("");}if(tot%20!=0) puts("");return 0;
}