2022 天梯赛选拔赛

Problem G. 星月观星(20分)

元丰九四五年二月三十一日夜,解衣欲睡,月色入户,欣然起行。念无与为乐者,遂至埃栋找锦乐。锦乐已寝,相与逐于中庭。

庭下星空璀璨,繁星密布,叹为观止也。看见这美丽的星与月,白茶十分想拍照一张。然而愤怒的锦乐把白茶的手机摔了,所以白茶只能用星月的摄影功能来拍照。

虽然可见范围的星空为 n\times m 的矩阵,但星月的摄像头分辨率为 k\times k ,所以拍照只能截得星空中一个 k\times k 的子矩阵。矩阵上元素若为 * ,代表此处有一颗星星;若为 o ,代表此处有一个月亮;若为 . ,代表此处什么也没有。白茶想用星月拍摄一张有月亮且星星数目最多的照片,请问在有月亮的条件下,星月最多能拍到多少颗星星。

输入

输入一行三个整数 n,m,k(1\le n,m\le50,1\le k\le\min{(n,m)}) ,代表矩阵的大小和摄像头分辨率。

接下来输入 n 行,每行 m 个字符,字符的取值范围为 . , *o ,保证 o 出现且仅出现一次。

输出

输出一行一个整数,代表在有月亮的条件下,星月最多能拍到的星星数目

样例

标准输入 复制文本
4 5 2
**..*
**.*.
..*o*
*..*.
标准输出 复制文本
2

登录以提交代码。
单点时限 1 秒
内存限制 256 MB
提交 152
通过 47

A B C D E F G H I J K L M N O

题目存在部分分,请使用合适的做题策略答题