Go Stone Puzzle

题目描述

有 $N+2$ 个按一行排列的格子。令格子 $i$ 表示从左数第 $i$ 个格子。 在格子 $1$ 到格子 $N$ 的每个格子中各放有一块石子。
对于每个 $1 \leq i \leq N$，如果 $S_i$ 是 $W$ 则格子 $i$ 中的石子为白色，如果 $S_i$ 是 $B$ 则为黑色。
格子 $N+1$ 和 $N+2$ 为空。 你可以任意次（可能为零次）执行以下操作：

选择一对相邻且都包含石子的格子，并将这两块石子移动到那两个空格子，同时保持它们的顺序。
更精确地，选择一个整数 $x$ 使得 $1 \leq x \leq N+1$ 且格子 $x$ 和 $x+1$ 都包含石子。令 $k$ 和 $k+1$ 为那两个空的格子。将格子 $x$ 和 $x+1$ 的石子分别移动到格子 $k$ 和 $k+1$。

判断是否可以达到以下状态，如果可以，求出所需操作的最小次数：

格子 $1$ 到格子 $N$ 的每个格子都包含一块石子，并且对于每个 $1 \leq i \leq N$，格子 $i$ 中的石子在 $T_i$ 为 $W$ 时为白色，在 $T_i$ 为 $B$ 时为黑色。

输入格式

输入从标准输入按照以下格式给出： $N$ $S$ $T$

输出格式

如果可以达到目标状态，输出所需操作的最小次数。如果不可能，输出 $-1$。

6
BWBWBW
WWWBBB

4

6
BBBBBB
WWWWWW

-1

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

7

提示

$2 \leq N \leq 14$ $N$ 是整数。 字符串 $S$ 和 $T$ 的长度均为 $N$，且由字符 $B$ 和 $W$ 组成。用 $.$ 表示空格子，目标状态可以通过如下四次操作达到，这是最小次数：

$BWBWBW..$ $BW..BWBW$ $BWWBB..W$ $..WBBBWW$ $WWWBBB..$

标签: AtCoder|abc361D

来源

AtCoder|abc361D