OI题库

【题目描述】

在奶牛们回家休息之前，Farmer_Jnhn想让它们做一个智力游戏。

游戏的棋盘由地面上N (1≤N≤15个)相同的洞洞构成，初始状态均为空。游戏的玩法是：走一步要么是把一颗石子填在一个原来是空的洞洞里，要么是从原来不空的洞洞里取走石子。游戏的状态定义成哪些洞洞填了石子，哪些洞洞没有填石子。游戏的目标是达到所有可能的状态一次且仅一次，然后回到所有洞洞全为空的初始状态。

奶牛们玩这个游戏可费了脑筋了下面是一个例子：

洞洞

步数1 2 3

0 O O O 初始状念

1 O O X 放一棵石子在第3洞

2 X O X 放一颗石子在第1洞

3 X O O 取走第3洞的石子

4 X X O 放一颗行子住笫2洞

5 O X O 取走第1洞的石子

6 O X X 放一颗石子在第3洞

7 X X X 放一颗石子在第1洞

         现在，奶牛纠结了!它们必须从某个洞洞取走一颗石子，但无论取走哪颗石子，都要回到一个曾经到达过的状念。例如，如果取走笫2个洞洞的石子，到达状态(X O X)，这个状态在第2步已经出现过。

         以下是一个N=3的合法移动方案：

         洞洞

步数1 2 3

0 O O O 初始状态

1 O X O 放一颗石子在第2洞

2 O X X 放一颗石子在第3洞

3 O O X 取走第2洞的石子

4 X O X 放一颗石子在第1洞

5 X X X 放一颗石子在第2洞

6 X X O 取走第3洞的石子

7 X O O 取走第2洞的石子

8 O O O 取走第1洞的石子

             奶牛们玩得精疲力竭，想得到你的帮助。请你写一个程序，给定N,求出一个合法的移动顺序，来赢得游戏。如果有多个方案，任求一个即可。

【输入格式】

第1行：一个整数N

【输出格式】

第1--2^N+1行：每行一个长度为N的字符串，串中仅包含'O'和'X'(O代表空洞洞，X表示不空的洞洞)。串中第j个字符表示第j个洞洞的状态。第1行和最后一行都是全'O'的状态。

【样例输入】

3

【样例输出】

OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO

【提示】

在此键入。

【来源】

在此键入。