该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P15890 [COCI 2025/2026 #6] 抄写 / Prepisivanje

题目描述

在克罗地亚语重要考试的前夕，教室已经准备就绪。我们可以将教室视为一个 $n \times m$ 的矩阵，每个单元格代表一个座位。矩阵的每个单元格可以取以下三种值之一：

• $2$ 表示已被行为良好的学生占用的座位。这些学生很负责，老师不担心他们。
• $1$ 表示老师标记为禁止入座的座位。这些座位无人就坐。
• $0$ 表示空座位，可供调皮学生就坐。

调皮学生尚未到达，但即将到来。老师可以决定哪些空座位将由调皮学生占据。

行为良好的学生从不作弊，但如果他们与调皮学生相邻，则可能导致调皮学生作弊。如果一个调皮学生至少有一个邻座（上、下、左、右四个方向之一），无论是行为良好的学生还是其他调皮学生，该调皮学生就会作弊。

请确定教室中可以就坐的学生总数（包括行为良好的学生和调皮学生）的最大值，使得考试期间不会发生作弊行为。

输入格式

第一行包含自然数 $n, m$（$1 \le n, m \le 80$），含义如题目描述所述。

接下来的 $n$ 行，每行包含 $m$ 个字符，每个字符为 $0$、$1$ 或 $2$，表示题目中描述的矩阵。

输出格式

输出一行一个整数，表示教室中可以就坐且考试期间不发生作弊行为的学生总数的最大值。

输入输出样例 #1

输入 #1

4 4
0100
0202
1000
2120

输出 #1

6

输入输出样例 #2

输入 #2

4 4
0000
0000
0000
0000

输出 #2

8

说明/提示

第二个样例的解释：老师将在第 1 行和第 3 行的奇数列安排学生，在第 2 行和第 4 行的偶数列安排学生。这样安排可以确保没有学生会作弊。

计分方式

翻译由 DeepSeek V3.2 完成