围棋棋子谜题

题目描述

有 $N+2$ 个格子排成一排。记从左数第 $i$ 个格子为格子 $i$。

在格子 $1$ 到格子 $N$ 中各放有一颗棋子。

对每个 $1 \leq i \leq N$,若 $S_i$ 为 W,则格子 $i$ 中的棋子为白色;若 $S_i$ 为 B,则为黑色。

格子 $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,则为黑色。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$
$T$

输出格式

若能达到目标状态,输出所需的最少操作次数;若不能,输出 -1。

样例

6
BWBWBW
WWWBBB

4

用 . 表示空格子,目标状态可以通过以下四次操作达到,这是最少次数:

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

6
BBBBBB
WWWWWW

-1

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

7

数据范围

• $2 \leq N \leq 14$
• $N$ 为整数。
• $S$ 和 $T$ 均为长度为 $N$、由 B 和 W 组成的字符串。