题目描述
地图背景:
塔防(TD)游戏魔兽版。一些囚犯被集体关在一个地下牢笼里,但它们准备集体出逃。你需要通过建塔,阻止它们进入道路终点处的微微发亮的传送门。
描述:
WZY这天正在Blizzard Tower Defense中疯狂地建塔,已经到Wave30了...他望着自己造的n多个箭塔(这个n与数据没关系。。。),看到这些箭塔攻击范围已经覆盖了整个地图的很多区域,竟然分辨不出有哪些箭塔了...他现在只知道箭塔的攻击范围是一个正方形(但边长>=2,每种箭塔的攻击范围边长是一定的)。WZY希望通过已知的攻击范围得出有哪些地方可能有箭塔。比如下面这个地图(含义在输入格式中):
01110
11110
11110
则攻击范围边长为2的箭塔最多可以有5个,攻击范围边长为3的箭塔最多可以有1个。
注意对“最多个数”的解释:
1、所有摆放的箭塔,攻击范围可以重叠
2、相同边长的箭塔,中心不能重叠
3、【不同边长的箭塔,中心可以重叠】
输入格式
输入数据第一行是地图的长、宽(地图抽象为一个n行m列的矩阵,长为n,宽为m,2<=n,m<=200)。接下来是这个n行m列的矩阵,在任意一个或多个箭塔攻击范围内的点为1,否则为0。下面是一个整数p(1<=p<=200),表示箭塔的种类数。接下来是p行,这p行中第i行表示第i种箭塔的攻击范围边长。
输出格式
输出数据p行,第i行表示第i种箭塔的最多可以摆放的个数,没有则为0。
样例输入
样例输出