[ABC361] D - Go Stone Puzzle

D - Go Stone Puzzle

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 425 分

题面

有 个单元格排成一排。设第 个单元格表示从左边数第 个单元格。

从单元格 到单元格 中分别放有一颗石头。
对于每个 ，如果 为 W，则单元格 中的石头为白色；如果 为 B，则单元格 中的石头为黑色。
单元格 和 是空的。

你可以进行以下操作任意次数（可以为零）：

• 选择一对相邻的含有石头的单元格，并将这两颗石头移动到空的两个单元格上，保持它们的顺序不变。
  更具体地，选择一个整数 ，使得 ，并且单元格 和 都含有石头。设 和 是两个空单元格。将单元格 和 中的石头分别移动到单元格 和 中。

判断是否可能达到如下状态，并如果可能，找出所需的最少操作次数：

• 每个从单元格 到单元格 中都含有一颗石头，并且对于每个 ，如果 为 W，则单元格 中的石头为白色；如果 为 B，则单元格 中的石头为黑色。

限制条件

• 为整数。
• 和 中的每一个都是由长度为 的由 B 和 W 构成的字符串。

---

输入

输入由标准输入给出，格式如下：

输出

如果可以达到所需状态，则打印所需的最少操作次数。如果不可能，则打印 -1。

---

输入样例 1

6
BWBWBW
WWWBBB

输出样例 1

4

用 . 表示一个空单元格，所需状态可以通过以下四个操作实现，这是最少次数：

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

---

输入样例 2

6
BBBBBB
WWWWWW

输出样例 2

-1

---

输入样例 3

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

输出样例 3

7