103613: [Atcoder]ABC361 D - Go Stone Puzzle
Description
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$ isB
.
Constraints
- $2 \leq N \leq 14$
- $N$ is an integer.
- Each of $S$ and $T$ is a string of length $N$ consisting of
B
andW
.
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
Output
问题陈述
有$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