能养几只公羊

题目描述

有一个农夫有个 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≤n,m≤1000。

接下来是一个 n×m 的矩阵，矩阵里每个值是 0 或者 1。

输出格式

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

样例输入 #1

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

样例输出 #1

3

数据范围

1 ≤ n, m ≤ 1000

知识点与难度

本题涉及的知识点从属于 GESP二级（BFS/DFS搜索、连通分量），难度等级：⭐⭐⭐。

测试点分布