← 返回题目列表

AtCoder · icpc2013summer_day4_j

J. 旋转游戏

中文机器翻译题面 查看原题

问题陈述

你有一块高度为 2 宽度为 2 的板 W。 该板被分为 1x1 单元。 棋盘从上到下每行编号为 1 和 2,每列编号为 1 到 W 从左到右。 我们表示一个单元格 i- 第行 j第列 (i, j)。 最初,一些棋子被放置在棋盘的一些单元上。 这里我们假设每个棋子看起来都一样。 所以我们不区分每个检查器。 您可以在该板上进行以下操作:

  1. 正方形旋转:在棋盘上选择一个 2x2 的正方形。然后在 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} is o。否则, s_{ij} is .。然后是一个空行。以下两行包含所需排列的信息。类似地,如果一个细胞 (i, j) 最后必须包含一个检查器, t_{ij} is o。如果一个细胞 (i, j) 最后不能包含检查器, t_{ij} is .。如果细胞没有条件 (i, j), t_{ij} is *。 您可能会假设解决方案始终存在。

输出

在一行中输出所需的最少操作数。


示例输入 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