|
||||||||||
郑厂长系列故事——排兵布阵Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 5211 Accepted Submission(s): 1761 Problem Description 郑厂长不是正厂长 也不是副厂长 他根本就不是厂长 事实上 他是带兵打仗的团长 一天,郑厂长带着他的军队来到了一个n*m的平原准备布阵。 根据以往的战斗经验,每个士兵可以攻击到并且只能攻击到与之曼哈顿距离为2的位置以及士兵本身所在的位置。当然,一个士兵不能站在另外一个士兵所能攻击到的位置,同时因为地形的原因平原上也不是每一个位置都可以安排士兵。 现在,已知n,m 以及平原阵地的具体地形,请你帮助郑厂长计算该阵地,最多能安排多少个士兵。 Input 输入包含多组测试数据; 每组数据的第一行包含2个整数n和m (n <= 100, m <= 10 ),之间用空格隔开; 接下来的n行,每行m个数,表示n*m的矩形阵地,其中1表示该位置可以安排士兵,0表示该地形不允许安排士兵。 Output 请为每组数据计算并输出最多能安排的士兵数量,每组数据输出一行。 Sample Input
Sample Output
Source | ||||||||||
|