3045 - 排兵布阵

团长带兵来到n×m的平原作战。每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然,一个士兵不能站在另外一个士兵所能攻击到的位置,同时因为地形的原因平原上也不是每一个位置都可以安排士兵。 现在,已知n, m(n <= 100, m <= 10 )以及平原阵地的具体地形,请你帮助团长计算该阵地最多能安排多少个士兵。

输入

包含多组测试数据。每组数据的第一行包括两个整数n和m,接下来的n行,每行m个数,表示n*m的矩形阵地,其中1表示该位置可以安排士兵,0表示该地形不允许安排士兵。

输出

对每组测试数据,输出最多能安排的士兵数量。

样例

输入

6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

输出

2

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题