← 返回题目列表

Codeforces · 1739/E

E. 清洁机器人

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

考虑一个走廊,它可以表示为具有 $$$2$$$ 行和 $$$n$$$ 列的矩阵。我们将第 $$$i$$$ 行和第 $$$j$$$ 列交叉处的单元格表示为 $$$(i, j)$$$。单元格 $$$(i_1, j_1)$$$ 和 $$$(i_2, j_2)$$$ 之间的距离为 $$$|i_1 - i_2| + |j_1 - j_2|$$$。

牢房$$$(1, 1)$$$中有一个清洁机器人。走廊的一些牢房是干净的,其他牢房是脏的(有机器人的牢房是干净的)。您想要清洁走廊,因此您将启动机器人来执行此操作。

机器人启动后,工作原理如下。当至少一个单元格脏时,机器人会在脏单元格中选择最接近的(与其当前单元格),移动到那里并清洁它(因此该单元格不再脏)。清洁完一个单元后,机器人会再次找到距离当前单元最近的脏单元,依此类推。重复这个过程,直到整个走廊都干净为止。

然而,机器人的程序中存在一个严重的错误。如果在某个时刻,有多个最接近(距离机器人当前位置)的脏单元,则机器人会发生故障。

您希望以机器人不会发生故障的方式清洁走廊。在启动机器人之前,您可以自己清理一些(可能是零)脏的单元格。然而,当你有这个漂亮、聪明(但有缺陷)的机器人来做这件事时,你不想自己做太多脏活。请注意,您不能弄脏干净的电池。

计算在启动机器人之前可以留下脏东西的最大可能数量,这样它就不会发生故障。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 走廊中的柱数。

接下来是两行,表示走廊的 $$$1$$$-st 和 $$$2$$$-nd 行。这些行每行包含 $$$n$$$ 个字符,其中 0 表示干净单元格,1 表示脏单元格。机器人 $$$(1, 1)$$$ 的起始单元是干净的。

输出

打印一个整数——在启动机器人之前可以保留脏的最大可能数量的单元格,这样它就不会发生故障。

示例

输入 #1

2
01
11

输出 #1

2

输入 #2

2
01
01

输出 #2

2

输入 #3

4
0101
1011

输出 #3

4

输入#4

4
0000
0000

输出#4

0

输入 #5

5
00011
10101

输出 #5

4

输入 #6

6
011111
111111

输出 #6

8

输入#7

10
0101001010
1010100110

输出 #7

6

注意

在第一个示例中,您可以清理单元格 $$$(1, 2)$$$,因此机器人的路径为 $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2)$$$。

在第二个示例中,您可以保持走廊不变,因此机器人的路径为 $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$$$。

在第三个示例中,您可以清理单元格 $$$(1, 2)$$$,因此机器人的路径为 $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (1, 4)$$$。

在第四个示例中,走廊已经干净了。也许您之前已经启动了机器人?