CF1739E Cleaning Robot

考虑一个走廊，可以表示为一个有 $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$ 行和第 $2$ 行的状态。每行包含 $n$ 个字符，$0$ 表示该格子是干净的，$1$ 表示该格子是脏的。机器人的起始格子 $(1, 1)$ 是干净的。

输出一个整数，表示在不让机器人故障的前提下，启动机器人前你最多能留下的脏格子数。

在第一个样例中，你可以清理格子 $(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)$。 在第四个样例中，走廊已经全是干净的。也许你已经提前启动过机器人了？ 由 ChatGPT 4.1 翻译