问题描述

你有一个高度为2，宽度为$W$的棋盘。棋盘被分成1x1的小格子。棋盘的每一行从上到下编号为1和2，每一列从左到右编号为1到$W$。我们用$(i, j)$表示棋盘上第$i$行第$j$列的小格子。最初，一些棋子被放置在棋盘的某些小格子上。在这里，我们假设每个棋子看起来都是一样的，所以我们不区分每个棋子。你可以对棋盘进行以下操作：

1. 方形旋转：选择棋盘上的一个2x2的方形。然后使方形内的棋子按顺时针或逆时针方向旋转90度。

   

2. 三角形旋转：选择棋盘上构成一个三角形的一组小格子。在这里，我们称一个小格子的集合为三角形，如果它是由一个2x2的方形去掉一个小格子得到的。与方形旋转类似，可以按顺时针或逆时针方向旋转所选三角形中的棋子。

   

这个问题的目标是通过执行一系列旋转操作，将棋子的排列转变为期望的排列。初始排列和目标排列的信息作为输入给出。对于期望的排列，对于每个小格子$(i, j)$，指定以下情况之一：i. 小格子$(i,j)$必须包含一个棋子；ii. 小格子$(i,j)$不能包含一个棋子；iii. 对于小格子$(i, j)$没有约束条件。计算移动棋子所需的最小操作数，以使排列满足约束条件，并将其输出。

---

输入

输入的格式如下。

$W$ $s_{11}s_{11}...s_{1W}$ $s_{21}s_{21}...s_{2W}$

$t_{11}t_{11}...t_{1W}$ $t_{21}t_{21}...t_{2W}$

输入的第一行包含一个整数$W$（$2 \leq W \leq 2,000$），表示棋盘的宽度。接下来的两行包含初始排列的信息。如果初始排列中的一个小格子$(i, j)$包含一个棋子，$s_{ij}$为o。否则，$s_{ij}$为.。然后是一个空行。接下来的两行包含期望排列的信息。类似地，如果最后一个小格子$(i, j)$必须包含一个棋子，则$t_{ij}$为o。如果最后一个小格子$(i, j)$不能包含一个棋子，则$t_{ij}$为.。如果对于小格子$(i, j)$没有条件，则$t_{ij}$为*。你可以假设至少存在一个解。

输出

输出所需的最小操作数，一行表示。

---

示例输入1

3
.oo
o..

o.o
o..

示例输入1的输出

1

---

示例输入2

5
.o.o.
o.o.o

o.o.o
.o.o.

示例输入2的输出

3

---

示例输入3

4
o.o.
o.o.

.*.o
.o.*

示例输入3的输出

4

---

示例输入4

20
oooo.....ooo......oo
.o..o....o..oooo...o

...o*.o.oo..*o*.*o..
.*.o.o.*o*o*..*.o...

示例输入4的输出

25

---

示例输入5

30
...o...oo.o..o...o.o........o.
.o.oo..o.oo...o.....o........o

**o.*....*...*.**...**....o...
**..o...*...**..o..o.*........

示例输入5的输出

32

---

来源

Summer Camp 2013

---