#2375. 黑白棋子的移动
黑白棋子的移动
版权信息
来源: 自定义题目 题目名称: 黑白棋子的移动
任务总览表
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
黑白棋子的移动 | 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
个●
(黑子)在右边。 - 在每一步中,我们移动相邻的两个棋子,且每次必须跳过若干个棋子(不能平移)。
- 我们需要记录每一步的棋子状态,直到最后棋子的排列变成黑白相间的状态。
解法
- 初始化棋子排列:将前 n 个位置设为白子(
○
),后 n 个位置设为黑子(●
)。 - 每一步的移动:通过模拟相邻的两个棋子的移动,每次打印当前的棋子排列。
- 终止条件:当所有棋子排成黑白相间的状态时结束。
时间复杂度分析
- 每一步的移动和打印操作是 O(n),最多需要 n-1 步,因此整体时间复杂度为 O(n^2)。 对于 n ≤ 100,该算法在 时间限制内 是可行的。
结论
通过模拟每一步棋子的移动并打印过程,可以得到最终的黑白相间的棋子排列,确保每一步的状态符合要求。