2443: 能养几只公羊

题目描述

有一个农夫有个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×m，其中 1\le 1≤n,m≤1000。
接下来是一个n×m 的矩阵，矩阵里每个值是 0 或者 1。

输出描述

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