Letter Pair Move Game

题目描述

有 2n 个盒子排成一行。相邻的两个盒子是空的，所有其他盒子里都有字母 "A" 或 "B"。两种字母恰好分别出现在 n-1 个盒子中。 你的任务是移动字母，使得所有字母 "A" 出现在任意字母 "B" 之前。每一步你可以选择任意两个相邻且有字母的盒子，并将这两个字母按原顺序移动到相邻的两个空盒子。 可以证明，要么存在一个由至多 10n 步组成的解，要么不存在解。

输入格式

第一行是一个整数 n：共有 2n 个盒子。 第二行是一个长度为 2n 的字符串，描述初始位置。每个字符是 "A"、"B" 或 "."（空盒子）。

输出格式

首先输出一个整数 k：步数。随后输出 k 行描述每一步的移动。只要 k \le 1000，你可以输出任意解。 如果不存在解，仅输出 "-1"。

3
AB..BA

2
ABBA..
A..ABB

提示

$1 \le n \le 100$

标签: CSES2427|附加题1

来源

CSES2427|附加题1