Pond

2072. 【2016.10.6NOIP普及模拟】Pond 
(File IO): input:pond.in output:pond.out

时间限制: 1000 ms  空间限制: 262144 KB  具体限制   Goto ProblemSet

题目描述

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表示石块，下划线_表示空位。

样例输入

 
6

样例输出

 
XXXXXXOOOOOO__
XXXXX__OOOOOXO
XXXXXOOOOO__XO
XXXX__OOOOXOXO
XXXXOOOO__XOXO
XXX__OOOXOXOXO
XXXOXOO__OXOXO
X__OXOOXXOXOXO
XOXOXO__XOXOXO
__XOXOXOXOXOXO

数据范围限制

pond

这题就是等于纯打表，也可以说是循环打表。首先我们可以发现，开头和结尾时永远不会变的，XXX……OOO……__

例如 6 开头是XXXXXXOOOOOO__

结尾是__XOXOXOXOXOXO

所以过程就是每次做分两段为一组，也就是：

XXXXXXOOOOOO__

XXXXX__OOOOOXO
XXXXXOOOOO__XO

也就是 （1）找到XO和__，交换。

       （2）从后往前找，找到第一个OO，再找到__，交换。即可。

但我们发现，XXX__OOOXOXOXO以后的都不相同，完全没有规律。所以简单地打表就行了。也就是

XXXOXOO__OXOXO

X__OXOOXXOXOXO

XOXOXO__XOXOXO

__XOXOXOXOXOXO

在后面删掉两个XO

XXXOXOO__O

X__OXOOXXO

XOXOXO__XO

__XOXOXOXO

最后没次循环N-4次，输出XO即可。


var
        n,i,j,k:longint;
        s:string;
        s1,s11,s2,s22:char;
begin
        assign(input,'pond.in');reset(input);
        assign(output,'pond.out');rewrite(output);
        readln(n);
        for i:=1 to n do
                s:=s+'X';
        for i:=1 to n do
                s:=s+'O';
        s:=s+'__';
        writeln(s);
        for i:=1 to n do
        begin
                for j:=1 to n+1 do
                        if s[j]='O' then break;
                if j>5 then
                begin
                        for j:=1 to length(s) do
                                if s[j]='_' then
                                        break;
                        s1:=s[j];
                        s11:=s[j+1];
                        for k:=1 to length(s) do
                                if s[k]='O' then
                                        break;
                        s2:=s[k-1];
                        s22:=s[k];
                        s[j]:=s2;
                        s[j+1]:=s22;
                        s[k-1]:=s1;
                        s[k]:=s11;
                        writeln(s);
                        for j:=1 to length(s) do
                                if s[j]='_' then break;
                        s1:=s[j];
                        s11:=s[j+1];
                        for k:=j to length(s) do
                                if s[k]='X' then break;
                        s2:=s[k-1];
                        s22:=s[k-2];
                        s[j]:=s2;
                        s[j+1]:=s22;
                        s[k-1]:=s1;
                        s[k-2]:=s11;
                        writeln(s);

                end
                else
                begin
                        write('XXX__OOOXO');
                        for j:=1 to n-3-1 do
                                write('XO');
                        writeln;
                        write('XXXOXOO__O');
                        for j:=1 to n-3-1 do
                                write('XO');
                        writeln;
                        write('X__OXOOXXO');
                        for j:=1 to n-3-1 do
                                write('XO');
                        writeln;
                        write('XOXOXO__XO');
                        for j:=1 to n-3-1 do
                                write('XO');
                        writeln;
                        write('__XOXOXOXO');
                        for j:=1 to n-3-1 do
                                write('XO');
                        writeln;
                        halt;
                end;
        end;
        close(input);
        close(output);
end.

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注