AT_abc361_d [ABC361D] Go Stone Puzzle

题目描述

有 $N+2$ 个格子横向排列成一行。从左到右第 $i$ 个格子记为格子 $i$。

在格子 $1$ 到格子 $N$ 中，每个格子上各有一颗石子。
对于每个 $1 \leq i \leq N$，若 $S_i$ 为 W，则格子 $i$ 上的石子为白色；若 $S_i$ 为 B，则格子 $i$ 上的石子为黑色。
格子 $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，则格子 $i$ 上的石子为黑色。

输入格式

输入按以下格式从标准输入读入。

$N$ $S$ $T$

输出格式

如果可以达到目标状态，则输出所需的最小操作次数；如果无法达到，则输出 $-1$。

输入输出样例 #1

输入 #1

6
BWBWBW
WWWBBB

输出 #1

4

输入输出样例 #2

输入 #2

6
BBBBBB
WWWWWW

输出 #2

-1

输入输出样例 #3

输入 #3

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

输出 #3

7

说明/提示

限制条件

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

样例说明 1

用 . 表示没有石子的格子。可以按如下方式用 $4$ 次操作达到目标状态，且这是最小次数。

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

由 ChatGPT 4.1 翻译