分数: 425 点
问题陈述
有 N+2 单元格排列成一行。让细胞 i 表示 i左侧第一个单元格。
牢房中的每个牢房中都放置了一颗石头 1 到单元格 N.
对于每个 1 \leq i \leq N,牢房里的石头 i 为白色,如果 S_i is W,如果 S_i is 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,牢房里的石头 i 为白色,如果 T_i is
W,如果 T_i isB.
约束
- 2 \leq N \leq 14
- N 是一个整数。
- 每个 S 和 T 是一个长度为的字符串 N 组成
B和W.
输入
输入由标准输入按以下格式给出:
N S T
输出
如果可以达到期望的状态,则打印所需的最少操作数。如果不可能,则打印 -1.
示例输入 1
6 BWBWBW WWWBBB
示例输出 1
4
使用 . 来表示一个空单元格,可以通过如下四种操作来实现所需的状态,这是最小值:
BWBWBW..BW..BWBWBWWBB..W..WBBBWWWWWBBB..
示例输入 2
6 BBBBBB WWWWWW
示例输出 2
-1
示例输入 3
14 BBBWBWWWBBWWBW WBWWBBWWWBWBBB
示例输出 3
7