寻找潜艇

成绩 100 开启时间 2016年05月31日 星期二 19:35
折扣 0.8 折扣时间 2016年05月31日 星期二 19:35
允许迟交 是 关闭时间 2016年05月31日 星期二 19:35
输入文件 story.in 输出文件 story.out

【题目描述】寻找潜艇(story.cpp/c/pas)

　　楚继光率领的舰队在活动海域执行水上打击任务，众所周知，如果遇到了修罗王军团的潜艇，将会让本来就困难的任务更加困难，根据水上侦察机返回的情报，楚继光想要知道最多可能遇到多少潜艇。

   　 活动海域是一个n×m大小的矩形区域，根据侦察机返回的情报，我们已经知道了其中某些位置是礁石，潜艇不能在这个位置存在（这些位置将用1表示），而剩下的位置是潜艇可能出现的位置，潜艇占用2×3大小的格子，可以横着也可以竖着，但是不能被分割。但是，由于是潜水艇，两艘潜艇之间可以出现交错而不影响其活动。

【输入格式】

输入文件为story.in,第一行是两个整数n,m表示活动海域的大小为n×m

接下来n行m列，输入一个只有0或1的矩阵，表示侦察机返回的数据

【输出格式】

输出文件为story.out,输出一个数，表示最多遇到的潜艇数。

【样例输入】

6 6

0 0 0 1 0 0

0 1 0 0 0 0

0 0 0 0 0 1

0 0 0 0 0 1

0 0 0 0 0 0

0 0 0 1 0 0

【样例输出】

16

【数据范围】

20%的数据，n=2,m=3

100%的数据，n<=150,m<=10