AT_abc361_d [ABC361D] Go Stone Puzzle

有 $N+2$ 个格子横向排列成一行。从左到右第 $i$ 个格子记为格子 $i$。 在格子 $1$ 到格子 $N$ 中，每个格子上各有一颗石子。 对于每个 $1 \leq i \leq N$，若 $S_i$ 为 `W`，则格子 $i$ 上的石子为白色；若 $S_i$ 为 `B`，则格子 $i$ 上的石子为黑色。 格子 $N+1$ 和 $N+2$ 上没有任何东西。 你可以进行任意次数（可以为 $0$ 次）如下操作： - 选择一对相邻且都放有石子的格子，将这两个石子按原顺序移动到一对相邻的空格子上。 更准确地说，选择一个 $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$，若 $T_i$ 为 `W`，则格子 $i$ 上的石子为白色，若 $T_i$ 为 `B`，则格子 $i$ 上的石子为黑色。

输入按以下格式从标准输入读入。 > $N$ $S$ $T$

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

## 限制条件 - $2 \leq N \leq 14$ - $N$ 是整数 - $S,T$ 均为仅由 `B` 和 `W` 组成的长度为 $N$ 的字符串 ## 样例说明 1 用 `.` 表示没有石子的格子。可以按如下方式用 $4$ 次操作达到目标状态，且这是最小次数。 - `BWBWBW..` - `BW..BWBW` - `BWWBB..W` - `..WBBBWW` - `WWWBBB..` 由 ChatGPT 4.1 翻译