← 返回题目列表

Codeforces · 359/A

A. 表

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

Simon 有一个由 n 行和 m 列组成的矩形桌子。西蒙从 1 开始,从上到下对表格的行进行编号,从左到右,从 1 开始对表格的列进行编号。我们将第 x 行和第 y 列上的单元格表示为一对数字 (x, y)。表格角是单元格:(1, 1)、(n, 1)、(1, m)、(n, m)。

Simon 认为该表中的某些单元格很好。此外,众所周知,桌子的角落是没有好单元格的。

最初,表格的所有单元格都是无色的。西蒙想要为他的表格中的所有单元格着色。一步操作中,他可以选择表格中任意一个好的单元格 (x1, y1)、表格的任意角 (x2, y2) 并对表格中的所有单元格 (p, q) 进行着色,这些单元格满足以下两个不等式:min(x1, x2) ≤ p ≤ max(x1, x2)、min(y1, y2) ≤ q ≤ max(y1, y2)。

帮助西蒙!求为表格的所有单元格着色所需的最少操作数。请注意,您可以对一个单元格进行多次着色。

输入

第一行恰好包含两个整数 n, m (3 ≤ n, m ≤ 50)。

接下来的 n 行包含表格单元格的描述。具体来说,第 i 行包含 m 个空格分隔的整数 ai1,ai2,...,aim。如果 aij 等于 0,则单元格 (i, j) 不好。否则 aij 等于 1。保证至少有一颗电池是好的。保证没有一个好小区是死角。

输出

打印一个数字——西蒙实现他的想法所需的最少操作数。

示例

输入 #1

3 3
0 0 0
0 1 0
0 0 0

输出 #1

4

输入 #2

4 3
0 0 0
0 0 1
1 0 0
0 0 0

输出 #2

2

注意

在第一个示例中,操作顺序可以如下所示:

- 第一次需要选择单元格 (2, 2) 和角点 (1, 1)。
- 第二次您需要选择单元格 (2, 2) 和角点 (3, 3)。
- 第三次您需要选择单元格 (2, 2) 和角点 (3, 1)。
- 第四次您需要选择单元格 (2, 2) 和角点 (1, 3)。

在第二个示例中,操作顺序可以如下所示:

- 第一次需要选择单元格 (3, 1) 和角点 (4, 3)。
- 第二次需要选择单元格 (2, 3) 和角点 (1, 1)。