#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(黑子)在右边。
  • 在每一步中,我们移动相邻的两个棋子,且每次必须跳过若干个棋子(不能平移)。
  • 我们需要记录每一步的棋子状态,直到最后棋子的排列变成黑白相间的状态。

解法

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

时间复杂度分析

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

结论

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