网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[Citric S2]天空中的繁星
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | stara.in | 输出文件 | stara.out |
【题目背景】
第二届『Citric』杯NOIP提高组模拟赛 第二题【题目描述】
Lemon最近买了一台数码相机。某天Lemon很无聊,于是对着夜空拍了一张照片,然后把照片导入了电脑。Lemon想依靠电脑的力量,完成他小时候经常做却从来没有成功过的事情:数天空中有多少颗星星。
Lemon已经把相片处理成了黑白的,也就是说,每个像素只可能是两个颜色之一,白或黑。
Lemon定义像素(x,y)处是一颗星星,当且仅当,像素(x,y),(x-1,y),(x+1,y),(x,y-1),(x,y+1)都是白色的。因此一个白色像素有可能属于多个星星,也有可能有的白色像素不属于任何一颗星星。
借助电脑的力量,数出有多少颗星星对Lemon实在太容易了,他很快就完成了。
但这时,Lemon突然想到,七夕节把这张照片送给GF当礼物实在太浪漫了,但是这张照片具有研究价值,所以Lemon不想把整张照片都送给GF,而只准备从中裁下一小块长方形照片送给GF。但为了保证浪漫的效果,Lemon认为,他送给GF的那一小块相片中至少应该有k颗星星。
现在Lemon想知道,到底有多少种方法裁下这一小块长方形相片呢?
【输入格式】
输入文件第一行包含三个正整数n,m,k,意义见题目所示。接下来n行,每行一个长度为m的字符串,字符串仅由'.'和'*'构成,'.'表示这个像素为黑色,'*'表示这个像素为白色。
【输出格式】
输出文件仅包含一个整数,表示Lemon有多少种满足题意的裁剪方法。【输入样例】
5 6 3***...
****..
.**.*.
******
.*.***
【输出样例】
3【样例解释】
图中共有4颗星星,分别位于第2行第2列、第2行第3列、第4行第2列、第4行第5列。有3种符合题意的选择方法(以左上角行列 - 右下角行列方式给出): (1,1)-(5,4) (1,1)-(5,5) (1,1)-(5,6)
【数据规模】
时间限制为3秒对于20%的数据,满足N,M<=20.
对于40%的数据,满足N,M<=100.
对于70%的数据,满足N,M<=200.
对于100%的数据,满足N,M<=500,0<k<N*M.
提醒:tyvj在评测时会开O2进行优化,因此建议选手在本机测试你的程序速度时也打开O2开关。