3045 - 排兵布阵
时间限制 : 1 秒
内存限制 : 128 MB
团长带兵来到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
来源
动规专题