D - Go Stone Puzzle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

N+2 個のマスが横一列に並んでいます。左から i 番目のマスをマス i と表します。

マス 1 からマス N には石が 1 個ずつ置かれています。
各 1\leq i \leq N について、S_i が W のときマス i に置かれている石の色は白であり、S_i が B のときマス i に置かれている石の色は黒です。
マス N+1,N+2 には何も置かれていません。

あなたは以下の操作を好きな回数(0 回でもよい)行うことができます。

  • 石が 2 個並んでいる箇所を選び、その 2 個の石を順序を保って空きマスに移す。
    より正確には次の通り。1 以上 N+1 以下の整数 x であって、マス x,x+1 の両方に石が置かれているものを選ぶ。石の置かれていないマスを k,k+1 とする。マス x,x+1 にある石をそれぞれマス k,k+1 に移動する。

以下の状態にすることが可能か判定し、可能なら操作回数の最小値を求めてください。

  • マス 1 からマス N には石が 1 個ずつ置かれており、各 1\leq i \leq N について、T_i が W のときマス i に置かれている石の色は白、T_i が B のときマス i に置かれている石の色は黒である。

制約

  • 2 \leq N \leq 14
  • N は整数である
  • S,T は B および W のみからなる長さ N の文字列である

入力

入力は以下の形式で標準入力から与えられる。

N
S
T

出力

目的の状態にすることが可能なら操作回数の最小値を出力せよ。不可能ならかわりに -1 を出力せよ。

入力例 1

6
BWBWBW
WWWBBB

出力例 1

4

石が置かれていないマスを . と表します。以下のようにして 4 回の操作で目的の状態にすることができ、これが最小回数です。

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

入力例 2

6
BBBBBB
WWWWWW

出力例 2

-1

入力例 3

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

出力例 3

7

Score : 425 points

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