Skip to content

1463: 小V数星星

题目

题目描述

小V喜欢蓝色的星空

小V最近买了一台数码相机。

某天小V想散散心,于是对着夜空拍了一张照片,然后把照片导入了电脑。

小V想依靠电脑的力量,完成他小时候经常做却从来没有成功过的事情:数天空中有多少颗星星。

小V已经把相片处理成了黑白的,也就是说,每个像素只可能是两个颜色之一,白或黑。

小V定义像素(x,y)处是一颗星星,当且仅当,像素(x,y),(x-1,y),(x+1,y),(x,y-1),(x,y+1)都是白色的。

因此一个白色像素有可能属于多个星星,也有可能有的白色像素不属于任何一颗星星。

借助电脑的力量,数出有多少颗星星对小V实在太容易了,他很快就完成了。

但这时,小V突然想到,可以把这样的一张照片作为礼物送给小J,但是这张照片具有纪念意义,所以小V想留一部分照片给自己,于是准备从中裁下一小块长方形照片送给小J。

为了表示自己的诚意,小V认为,他送给小J的那一小块相片中至少应该有k颗星星。

现在小V想知道,到底有多少种方法裁下这一小块长方形相片呢?

输入格式

输入文件第一行包含三个正整数N,M,k,N,M表示照片的大小

接下来n行,每行一个长度为m的字符串,字符串仅由\'.\'和\'\'构成,\'.\'表示这个像素为黑色,\'\'表示这个像素为白色。

输出格式

输出文件仅包含一个整数,表示小V有多少种满足题意的裁剪方法。

样例输入

5 6 3

***...

****..

.**.*.

******

.*.***

样例输出

3

数据范围

对于20%的数据,满足N,M<=20.

对于40%的数据,满N,M<=100. 对于70%的数据,满N,M<=200. 对于100%的数据,满足N,M<=500,0<k<N*M.

注释 Hint 图中共有4颗星星,分别位于第2行第2列、第2行第3列、第4行第2列、第4行第5列。 有3种符合题意的选择方法(以左上角行列 - 右下角行列方式给出): (1,1)-(5,4) (1,1)-(5,5) (1,1)-(5,6)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!