大小为3的棋盘游戏里有3个白色棋子，3个黑色棋子，和一个有7个格子一线排开的木盒子。3个白棋子被放在一头，3个黑棋子被放在另一头，中间的格子空着。
初始状态: WWW_BBB
目标状态: BBB_WWW
在这个游戏里有两种移动方法是允许的：
1. 你可以把一个棋子移到与它相邻的空格；
2. 你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。
大小为N的棋盘游戏包括N个白棋子，N个黑棋子，还有有2N+1个格子的木盒子。
这里是3-棋盘游戏的解，包括初始状态，中间状态和目标状态：
WWW BBB
WW WBBB
WWBW BB
WWBWB B
WWB BWB
W BWBWB
WBWBWB
BW WBWB
BWBW WB
BWBWBW
BWBWB W
BWB BWW
B BWBWW
BB WBWW
BBBW WW
BBB WWW
请编一个程序解大小为N的棋盘游戏(1 <= N <= 12)。要求用最少的移动步数实现。
格式
PROGRAM NAME: shuttle
INPUT FORMAT:(file shuttle.in)
一个整数N。
OUTPUT FORMAT:(file shuttle.out)
用空格在棋盘的位置(位置从左到右依次为1, 2, ..., 2N+1)表示棋盘的状态。输出棋盘的状态变换序列，每行20个数(除了最后一行)。
输出的解还应当有最小的字典顺序(即如果有多组移动步数最小的解，输出第一个数最小的解；如果还有多组，输出第二个数最小的解；...)。
SAMPLE INPUT
3
SAMPLE OUTPUT
3 5 6 4 2 1 3 5 7 6 4 2 3 5 4
【参考程序】：
/*
ID: XIONGNA1
PROG: shuttle
LANG: C++
*/
#include<iostream>
#include<cstring>
using namespace std;
struct node
{
char s[30];
int pos,dep;
} list[150001];
int ans[1001];
char st[30],start[30],end[30];
int n;
void cout_ans()
{
int c=0;
for (int i=2;i<=ans[0];i++)
{
printf("%d",ans[i]);
c++;
if (c%20==0 || i==ans[0]) printf("\n");
else printf(" ");
}
}
void find_path(int k)
{
if (list[k].dep==0)
{
ans[0]++; ans[ans[0]]=list[k].pos;
return ;
}
find_path(list[k].dep);
ans[0]++; ans[ans[0]]=list[k].pos;
}
void BFS()
{
int head,tail,p;
list[1].pos=n+1; list[1].dep=0;
memcpy(list[1].s,start,sizeof(list[1].s));
head=tail=1;
while (head<=tail)
{
p=list[head].pos;
if (p-1>0 && list[head].s[p-1]=='W')
{
memcpy(st,list[head].s,sizeof(st));
st[p]='W'; st[p-1]=' ';
tail++;
memcpy(list[tail].s,st,sizeof(list[tail].s));
list[tail].pos=p-1; list[tail].dep=head;
if (memcmp(list[tail].s,end,sizeof(list[tail].s))==0)
{
find_path(tail); return ;
}
}
if (p+2<=2*n+1 && list[head].s[p+2]=='B' && list[head].s[p+1]=='W')
{
memcpy(st,list[head].s,sizeof(st));
st[p]='B'; st[p+2]=' ';
tail++;
memcpy(list[tail].s,st,sizeof(list[tail].s));
list[tail].pos=p+2; list[tail].dep=head;
if (memcmp(list[tail].s,end,sizeof(list[tail].s))==0)
{
find_path(tail); return ;
}
}
if (p+1<=2*n+1 && list[head].s[p+1]=='B')
{
memcpy(st,list[head].s,sizeof(st));
st[p]='B'; st[p+1]=' ';
tail++;
memcpy(list[tail].s,st,sizeof(list[tail].s));
list[tail].pos=p+1; list[tail].dep=head;
if (memcmp(list[tail].s,end,sizeof(list[tail].s))==0)
{
find_path(tail); return ;
}
}
if (p-2>0 && list[head].s[p-2]=='W' && list[head].s[p-1]=='B')
{
memcpy(st,list[head].s,sizeof(st));
st[p]='W'; st[p-2]=' ';
tail++;
memcpy(list[tail].s,st,sizeof(list[tail].s));
list[tail].pos=p-2; list[tail].dep=head;
if (memcmp(list[tail].s,end,sizeof(list[tail].s))==0)
{
find_path(tail); return ;
}
}
head++;
}
}
int main()
{
freopen("shuttle.in","r",stdin);
freopen("shuttle.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
start[i]='W'; end[i]='B';
}
start[n+1]=end[n+1]=' ';
for (int i=n+2;i<=2*n+1;i++)
{
start[i]='B'; end[i]='W';
}
ans[0]=0;
BFS();
cout_ans();
return 0;
}
【参考程序】：
{
ID: XIONGNA1
PROG: shuttle
LANG: PASCAL
}
type node=record
s:array[1..30]of char;
dep,ps:longint;
end;
var list:array[1..150000] of node;
st,start,ends:array[1..30]of char;
ans:array[0..1001]of longint;
n,i:longint;
procedure cout_ans();
var i,c:longint;
begin
c:=0;
for i:=2 to ans[0] do
begin
write(ans[i]); inc(c);
if ((c mod 20=0)or(i=ans[0])) then writeln
else write(' ');
end;
end;
procedure find_path(k:longint);
begin
if (list[k].dep=0) then
begin
inc(ans[0]); ans[ans[0]]:=list[k].ps;
exit;
end;
find_path(list[k].dep);
inc(ans[0]); ans[ans[0]]:=list[k].ps;
end;
function check(x:longint):boolean;
var i:longint;
begin
for i:=1 to 2*n+1 do
if (list[x].s[i]<>ends[i]) then
begin
check:=false;
exit;
end;
check:=true;
end;
procedure scopy1(x:longint);
var i:longint;
begin
for i:=1 to 2*n+1 do st[i]:=list[x].s[i];
end;
procedure scopy2(x:longint);
var i:longint;
begin
for i:=1 to 2*n+1 do list[x].s[i]:=st[i];
end;
procedure BFS();
var p,head,tail:longint;
begin
head:=1;tail:=1;
list[1].dep:=0; list[1].ps:=n+1;
for i:=1 to 2*n+1 do list[1].s[i]:=start[i];
while head<=tail do
begin
p:=list[head].ps;
if ((p-1>0)and(list[head].s[p-1]='W')) then
begin
scopy1(head);
st[p]:='W'; st[p-1]:=' ';
inc(tail);
scopy2(tail);
list[tail].dep:=head; list[tail].ps:=p-1;
if (check(tail)) then
begin
find_path(tail); exit;
end;
end;
if ((p+2<=2*n+1)and(list[head].s[p+2]='B')and(list[head].s[p+1]='W')) then
begin
scopy1(head);
st[p]:='B'; st[p+2]:=' ';
inc(tail);
scopy2(tail);
list[tail].ps:=p+2; list[tail].dep:=head;
if (check(tail)) then
begin
find_path(tail); exit;
end;
end;
if ((p+1<=2*n+1)and(list[head].s[p+1]='B')) then
begin
scopy1(head);
st[p]:='B'; st[p+1]:=' ';
inc(tail);
scopy2(tail);
list[tail].dep:=head; list[tail].ps:=p+1;
if (check(tail)) then
begin
find_path(tail); exit;
end;
end;
if ((p-2>0)and(list[head].s[p-2]='W')and(list[head].s[p-1]='B')) then
begin
scopy1(head);
st[p]:='W'; st[p-2]:=' ';
inc(tail);
scopy2(tail);
list[tail].ps:=p-2; list[tail].dep:=head;
if (check(tail)) then
begin
find_path(tail); exit;
end;
end;
inc(head);
end;
end;
begin
assign(input,'shuttle.in');reset(input);
assign(output,'shuttle.out');rewrite(output);
//while not eof do
//begin
readln(n);
for i:=1 to n do
begin
start[i]:='W'; ends[i]:='B';
end;
start[n+1]:=' '; ends[n+1]:=' ';
for i:=n+2 to 2*n+1 do
begin
start[i]:='B'; ends[i]:='W';
end;
ans[0]:=0;
BFS();
cout_ans();
//end;
close(input);close(output);
end.