103613: [Atcoder]ABC361 D - Go Stone Puzzle

Problem Statement

There are $N+2$ cells arranged in a row. Let cell $i$ denote the $i$-th cell from the left.

There is one stone placed in each of the cells from cell $1$ to cell $N$.
For each $1 \leq i \leq N$, the stone in cell $i$ is white if $S_i$ is W, and black if $S_i$ is B.
Cells $N+1$ and $N+2$ are empty.

You can perform the following operation any number of times (possibly zero):

• Choose a pair of adjacent cells that both contain stones, and move these two stones to the empty two cells while preserving their order.
  More precisely, choose an integer $x$ such that $1 \leq x \leq N+1$ and both cells $x$ and $x+1$ contain stones. Let $k$ and $k+1$ be the empty two cells. Move the stones from cells $x$ and $x+1$ to cells $k$ and $k+1$, respectively.

Determine if it is possible to achieve the following state, and if so, find the minimum number of operations required:

• Each of the cells from cell $1$ to cell $N$ contains one stone, and for each $1 \leq i \leq N$, the stone in cell $i$ is white if $T_i$ is W, and black if $T_i$ is B.

Constraints

• $2 \leq N \leq 14$
• $N$ is an integer.
• Each of $S$ and $T$ is a string of length $N$ consisting of B and W.

Input

The input is given from Standard Input in the following format:

$N$
$S$
$T$

Output

If it is possible to achieve the desired state, print the minimum number of operations required. If it is impossible, print -1.

Sample Input 1

6
BWBWBW
WWWBBB

Sample Output 1

4

Using . to represent an empty cell, the desired state can be achieved in four operations as follows, which is the minimum:

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

Sample Input 2

6
BBBBBB
WWWWWW

Sample Output 2

-1

Sample Input 3

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

Sample Output 3

7

问题陈述

有$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$，如果$T_i$是W，则单元格$i$中的石头是白色的；如果$T_i$是B，则石头是黑色的。

约束条件

• $2 \leq N \leq 14$
• $N$是一个整数。
• $S$和$T$都是长度为$N$的字符串，由B和W组成。

输入

输入从标准输入以以下格式给出：

$N$
$S$
$T$

输出

如果可以达到期望的状态，打印所需的最小操作次数。如果不可能，打印-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