版权信息

​来源​: 自定义题目 ​题目名称​: 黑白棋子的移动

---

任务总览表

任务名称	时间限制	内存限制	分数
黑白棋子的移动	1 sec	256 MB	10 points

---

题目描述

有 2n 个棋子（n ≥ 4）排成一行，开始时，白子全部在左边，黑子全部在右边，如下图所示（以 n = 5 为例）：

○ ○ ○ ○ ○ ● ● ● ● ●

棋子的移动规则是：每次必须同时移动相邻的两个棋子，颜色不限。可以左移，也可以右移到空位上去，但不能交换两个棋子的左右位置。每次移动必须跳过若干个棋子（不能平移），要求最后能变成黑白相间的一行棋子，如 n = 5 时，变成：

○ ● ○ ● ○ ● ○ ● ○ ●

任务：编程打印出移动过程。

---

输入格式

输入一个整数 ​n​（4 ≤ n ≤ 100），表示棋子的数量的一半。

---

输出格式

按照移动过程输出每一步的棋子排列，格式如下：

step i: <棋子排列>

其中 i 是当前的步骤编号，从 0 开始。

---

样例输入

7

样例输出

step 0: ooooooo*******--
step 1: oooooo--******o*
step 2: oooooo******--o*
step 3: ooooo--*****o*o*
step 4: ooooo*****--o*o*
step 5: oooo--****o*o*o*
step 6: oooo****--o*o*o*
step 7: ooo--***o*o*o*o*
step 8: ooo*o**--*o*o*o*
step 9: o--*o**oo*o*o*o*
step 10: o*o*o*--o*o*o*o*
step 11: --o*o*o*o*o*o*o*

---

提示

• ​数据范围​：
  • ​n ≥ 4​，最大 ​n = 100​，表示棋子的数量可以达到 ​200​。
• ​棋子表示​：
  • 使用 ○ 表示白子，● 表示黑子，* 表示空位。

---

题目分析

目标

• 给定初始棋子排列，打印出每一步的棋子移动过程，直到最终排列为黑白相间的状态。

思路

• 初始棋子排列是由 n 个白子和 n 个黑子组成，初始排列为 n 个 ○（白子）在左边，n 个 ●（黑子）在右边。
• 在每一步中，我们移动相邻的两个棋子，且每次必须跳过若干个棋子（不能平移）。
• 我们需要记录每一步的棋子状态，直到最后棋子的排列变成黑白相间的状态。

解法

1. ​初始化棋子排列​：将前 n 个位置设为白子（○），后 n 个位置设为黑子（●）。
2. ​每一步的移动​：通过模拟相邻的两个棋子的移动，每次打印当前的棋子排列。
3. ​终止条件​：当所有棋子排成黑白相间的状态时结束。

---

时间复杂度分析

• 每一步的移动和打印操作是 ​O(n)​，最多需要 n-1 步，因此整体时间复杂度为 ​O(n^2)​。 对于 ​n ≤ 100​，该算法在 时间限制内 是可行的。

---

结论

通过模拟每一步棋子的移动并打印过程，可以得到最终的黑白相间的棋子排列，确保每一步的状态符合要求。