有2n个棋子(n>=4)排成一行,开始时白子全在左边,黑子全在右边,最右边有两个空格:
OOOO****__(n=4);
要求把它移成黑白相见的一行棋子:
__O*O*O*O*;
移动规则是:每次必须同时移动相邻的2个棋子,颜色不限;但不能调换2个棋子的左右位置。移动必须跳过若干个棋子到左边或右边的空位上去(不能平移)。
输入格式 Input Format
n小于等于100
输出格式 Output Format
初始到目标的所有步骤,具体看样例。
样例输入 Sample Input
4
样例输出 Sample Output
step 0:OOOO****__
step 1:OOO__***O*
step 2:OOO*O**__*
step 3:O__*O**OO*
step 4:O*O*O*__O*
step 5:__O*O*O*O*
分析:
有规律可寻。
![](http://www.cppblog.com/images/cppblog_com/xiongnanbin/112.jpg)
【参考程序】:
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
string s,ans;
int n;
int main()
{
cin>>n;
s="";
for (int i=0;i<n;i++) s+='O';
for (int i=0;i<n;i++) s+='*';
s+="__";
int x=n,tot=0;
cout<<"step "<<tot<<":"<<s<<endl;
tot++;
while (x>4)
{
s[x-1]='_'; s[x]='_'; s[2*x]='O'; s[2*x+1]='*';
cout<<"step "<<tot<<":"<<s<<endl;
tot++;
s[2*x-1]='_'; s[2*x-2]='_'; s[x-1]='*'; s[x]='*';
cout<<"step "<<tot<<":"<<s<<endl;
x--;
tot++;
}
ans=s.substr(10,(n-4)*2);
cout<<"step "<<tot<<":"<<"OOO__***O*"+ans<<endl; tot++;
cout<<"step "<<tot<<":"<<"OOO*O**__*"+ans<<endl; tot++;
cout<<"step "<<tot<<":"<<"O__*O**OO*"+ans<<endl; tot++;
cout<<"step "<<tot<<":"<<"O*O*O*__O*"+ans<<endl; tot++;
cout<<"step "<<tot<<":"<<"__O*O*O*O*"+ans<<endl; tot++;
return 0;
}
【参考程序】://pascal
var s,ans:string;
n,total,i,x:longint;
begin
readln(n);
for i:=1 to n do
s:=s + 'O';
for i:=1 to n do
s:=s + '*';
s:=s + '__';
x:=n;
writeln('step ',total,':',s);
inc(total);
while x > 4 do
begin
s[x]:='_'; s[x+1]:='_'; s[2*x+1]:='O'; s[2*x+2]:='*';
writeln('step ',total,':',s);
inc(total);
s[2*x]:='_'; s[2*x-1]:='_'; s[x]:='*'; s[x+1]:='*';
dec(x);
writeln('step ',total,':',s);
inc(total);
end;
ans:=copy(s,11,(n-4)*2);
writeln('step ',total,':OOO__***O*'+ans); inc(total);
writeln('step ',total,':OOO*O**__*'+ans); inc(total);
writeln('step ',total,':O__*O**OO*'+ans); inc(total);
writeln('step ',total,':O*O*O*__O*'+ans); inc(total);
writeln('step ',total,':__O*O*O*O*'+ans); inc(total);
end.