← 返回题目列表

AtCoder · pakencamp_2019_day3_d

D. 帕肯军旗

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

配点: 100 点

問題文

Chikkoma PA 实验室在不久的将来将面临 PA 实验室之战。为此,我们决定制作一面军旗。

旗帜设计是垂直的 5 件,水平 N 分成几块 它由 5 \times N 方块表示。从上面 i 第几行,从左到右 j 列中的单元格, 我们将其表示为(i, j) 。

目前,旗帜的每个方格都涂成红色、蓝色、白色或黑色。更具体地说,质量 (i, j) 是颜色 它涂有 S_{i, j} 。然而,S_{i, j} 是 R, B, W, # 表示它分别被漆成红色、蓝色、白色或黑色。

E869120 您想要将 PAKEN 标志重新绘制为蓝色、白色和红色,以便满足以下条件。 对于所有

  • N 列, 5 方块为“全蓝”、“全白”或“全红”
  • 哪个相邻 2 两列也有不同的颜色。

但是请注意,如果有黑色方块,则不满足条件。

以下是满足条件的标志和不满足条件的标志的示例。

  • 例 1 满足条件。 例如,
  • 例 2 从左侧开始 第 2 列中有蓝色和白色的方块,5 不满足两者必须相同的条件。
  • 例 3 从左侧开始 第 3 第左起列 第 4 列具有相同的颜色,因此不满足条件。 第
  • 例 4 从左侧开始 第 5 颜色是黑色,因此不满足条件。

E869120 您希望尽可能减少要重新绘制的方块数量,以缩短标志创建时间。
编写一个程序来查找需要重新绘制的最小方块数。

制約

所有输入数据满足以下约束。 满足

  • N 是 1 \leq N \leq 999 的整数
  • S_{i, j} 是 R, B, W, # 任何一个

部分点

该问题分为多个子任务,如果您正确回答了该子任务的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (11 点) N = 1 。
  2. (13 点) N = 3 。
  3. (29 点) N \leq 10 。
  4. (22 点) 5 对于所有行。 N 方块的颜色都是相同的。
  5. (25 分) 没有额外的限制。

但是,小作业 关于 4 , 小心不要误读为“N 列, 5 单元格都是相同的颜色。”


入力

输入是按以下格式从标准输入给出的。
但是,标志每行的颜色信息 S_{i, 1}, S_{i, 2}, S_{i, 3}, \dots, S_{i, N} 已连接 N 请注意,它是作为字符串输入的。

N
S_{1, 1} S_{1, 2} S_{1, 3} \cdots S_{1, N}
S_{2, 1} S_{2, 2} S_{2, 3} \cdots S_{2, N}
S_{3, 1} S_{3, 2} S_{3, 3} \cdots S_{3, N}
S_{4, 1} S_{4, 2} S_{4, 3} \cdots S_{4, N}
S_{5, 1} S_{5, 2} S_{5, 3} \cdots S_{5, N}

出力

创建北肯军旗帜时需要重新绘制的最小方格数为 请输出1 行。


入力例 1

1
B
R
#
W
B

出力例 1

3

下面 3 您可以制作街头公园旗帜。

  • 将所有方块设为红色。当时,大众 (1, 1), (3, 1), (4, 1), (5, 1) 的 可以考虑 4 有必要重新绘制方块。
  • 将所有方块设为蓝色。当时,大众 (2, 1), (3, 1), (4, 1) 的 可以考虑 3 有必要重新绘制方块。
  • 将所有方块设为白色。当时,大众 (1, 1), (2, 1), (3, 1), (5, 1) 的 可以考虑 4 有必要重新绘制方块。

其中,最好将所有方块都设为蓝色。此时需要重画的方格数为 将会有 3 块。

顺便说一句,这是 N = 1 因此,一个小任务 它满足 1 的约束。


入力例 2

3
WWR
#RW
BW#
##B
RBR

出力例 2

10

1 蓝色栏,2 柱白色,3 当该列为红色时,可以更改要重新绘制的方格数。 10 这是最好的选择。

(这里,“★”代表重新绘制的正方形。)

顺便说一句,这是 N = 3 因此,一个小任务 它满足 2 的约束。


入力例 3

8
RRRRRRRR
########
BBBBBBBB
RRRRRRRR
WWWWWWWW

出力例 3

28

最好如下图所示重画。需要重新绘制的方格数为 将会有 28 件。 (这里,“★”代表重新绘制的正方形。)


入力例 4

7
BR#WB#R
RWW#WRB
##WBR#W
WB#B#RW
BRW##BB

出力例 4

21

最好如下图所示重画。需要重新绘制的方格数为 将会有 21 件。 (这里,“★”代表重新绘制的正方形。)