【2016.10.6NOIP普及模拟】Pond

发布于 2019-04-12  852 次阅读


题目描述

G最后在规定时间内完成了任务,Alice只能放行。
出了房间,G的左边是一条继续前进的道路,右边是一个池塘。池塘中有序的排列着一排数量相同石块和荷叶。
正在G准备向左走继续前进的时候,D和Z爬完了楼梯,出现在了池塘的另一边。D和Z可以踩着石块通过池塘,并且每步可以跨两个单位长度(假定相邻两个物体之间的距离为一个单位长度)。
当前池塘中荷叶与石块的排列如下:(字母X为荷叶,O为石块)
XXXXXOOOOO
显而易见,D和Z是无法通过池塘的。正在她们一筹莫展的时候,G在岸边发现了一个机关。机关中的黑色白色石子分别代表石块和荷叶,移动石子便能够移动相应的石块与荷叶。移动规则如下:
石子靠右排列,左侧有两个空位,每次操作可以将相邻的任意两个石子移动到空位上,但左右位置不可交换。
由于G刚才搬完皇后石像,身心疲惫,她希望你帮她找到移动石子的步骤,使得D和Z可以踩着石头通过池塘。当然,时间紧迫,步骤越少越好。

输入

一个整数n(4≤n≤30),表示石块和荷叶的数量。

输出

输出移动步骤。
其中第一行为初始状态,从左到右一次为n个荷叶,n个石块,2个空位。
最后一行为末状态,规定末状态是2个空位在最左侧。
大写字母X表示荷叶,大写字母O表示石块,下划线_表示空位。

思路

当n=4时我们可以很容易的找出解决方法,而当n>4时可以两步把它变成n-1,一直进行上面的操作就可以了

const
  maxn=1000;
var
  b:array[1..maxn]of char;
  pt,i,n,num:integer;
procedure print;
var
  i:integer;
begin
  inc(num);
  for i:=1 to 2*(n+1) do write(b[i]);
  writeln;
end;
procedure move(k:integer);
var
  i:integer;
begin
  for i:=0 to 1 do
    begin
      b[pt+i]:=b[k+i];
      b[k+i]:='_';
    end;
  pt:=k;
  print;
end;
procedure mv(n:integer);
begin
  if n=4 then
    begin
      move(4);
      move(8);
      move(2);
      move(7);
      move(1);
    end
  else
    begin
      move(n);
      move(2*n-1);
      mv(n-1);
    end;
end;
begin
  assign(input,'pond.in'); reset(input);
  assign(output,'pond.out'); rewrite(output);
  readln(n);
  for i:=1 to n do b[i]:='X';
  for i:=n+1 to 2*n do b[i]:='O';
  b[i+1]:='_';
  b[i+2]:='_';
  pt:=2*n+1;
  num:=-1;
  print;
  mv(n);
end.
]]>