能养几只公羊

题目描述

有一个农夫有个$n×m$大小的农场，农场的四周有墙把农场跟外面隔离开，同时农场里也一些隔离墙，其余的是空地。 农夫想养一些公羊，但是公羊好斗，而且公羊在农场里会上、下、左、右四处走动（但不能穿过墙），两只公羊不能见面（见面就会顶角受伤），为了不让公羊受伤，农夫想知道他的农场最多能养几只公羊？ 为了方便起见，农场的描述用 $0$ 和 $1$ 表示，$0$ 表示空地，$1$ 表示墙。 例如，农夫有个 $4×5$ 的农场，图形如下： 1 0 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 0 0 这个农场可以养 $3$ 只公羊

输入格式

第一行输入 $n$ 和 $m$，表示农场大小是 $n\times m$，其中 $1\le n,m\le 1000$。 接下来是一个 $n\times m$ 的矩阵，矩阵里每个值是 $0$ 或者 $1$。

输出格式

一行，一个整数，表示农夫能养的公羊数量。

4 5
1 0 1 1 1
1 0 1 0 1
1 1 1 1 0
1 0 0 0 0

3

提示

（暂无提示）

来源

童程童美