U28551.进攻皇宫
普及+/提高
NOI Online
通过率:0%
时间限制:3.00s ~ 3.00s
内存限制:128MB
题目描述
起义军不满皇帝的暴力制度,发起了起义,起义军势如破竹,很快就打到了皇宫脚下。起义军看到皇帝的皇宫的奢华,十分愤怒,决定一把火烧了皇宫。
已知起义军可以用3个火把,每个火把可以点燃以自身为中点3×3的范围,皇宫大小为n×m。起义军的目标是尽可能烧掉更多奢侈品。为了更好达成目标,起义军已经在皇宫平面图上进行了标记:dollar符为奢侈品,“*”为空地。起义军已经统计好了奢侈品数量为t。请你帮起义军找到尽可能烧掉更多奢侈品的方法。
输入格式
第一行输入n、m、t和L(1<=n,m<=10000,0<=t,L<=n*m)
接下来输入一个n×m的矩阵,其中有t个dollar
输出格式
一行,输出最多能烧掉多少奢侈品(dollar)
输入输出样例
输入#1
5 9 11 ****$**$* $$$****** *******$* $$$****** ****$**$*
输出#1
9
说明/提示
火把可以放在奢侈品上