[ABC361D]Go Stone Puzzle

题目描述

有N+2个单元格排成一行。让单元格i表示从左边开始的第i个单元格。

从1格到N格，每个格中都放了一块石头。
对于每一个1≤i≤N，如果Si是 "W"，那么i单元格中的棋子就是白色的；如果Si​是 "B"，那么ii单元格中的棋子就是黑色的。
N+1和N+2单元格为空。

您可以执行以下操作任意多次(可能为零)：

• 选择一对都有棋子的相邻单元格，并将这两个棋子移动到空的两个单元格中，同时保留它们的顺序。
  更确切地说，选择一个整数x，使得1≤x≤N+1以及x和x+1两个单元格都包含棋子。假设k和k+1是空的两个单元格。将x和x+1两个单元格中的棋子分别移动到k和k+1两个单元格中。

判断是否可以达到下面的状态，如果可以，请找出所需的最小操作次数：

• 从单元格1到单元格N的每个单元格中都有一颗棋子，对于每个单元格1≤i≤N，如果Ti​为 "W"，则单元格ii中的棋子为白色；如果Ti​为 "B"，则单元格i中的棋子为黑色。

输入描述

第一行，一个整数N

第二行，字符串S

第三行，字符串T

数据范围：

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

输出描述

如果可以实现所需的状态，则打印所需的最少操作数。如果不可能，则打印-1。

提示

样例1：

用.表示空单元格，可以通过以下四次运算达到所需的状态，这是最小值：

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