5006 - 2022信息与未来T2:沙滩面积
时间限制 : 1 秒
内存限制 : 128 MB
我们获得了一个陆地和水域情况的卫星照片,照片可以看成是一个n行m列的矩形,矩形中的每个格子要么是陆地(用半角点.表示),要么是水域(用#表示)。
虽然卫星照片可以看清楚地辨别出陆地和水域,但陆地的具体类型却不明确,现在我们了解到,对于一块是水域的方格,它向上、下、左、右四个方向k布之内可达的陆地格子,均会形成沙滩。例如,下图展示了k=2的情况,蓝色的格子代表水域,标为黄色的陆地格子是沙滩!
你的任务是根据卫星照片计算出属于沙滩的格子数量,注意:卫星照片只拍摄了包含水域的部分,水域附近的沙滩可能出现在卫星照片的边界之外,你可以假设卫星照片之外不存在任何水域
输入
输入的第一行是空格分隔的三个整数n,m,k,代表拍摄的卫星照片共有n行m列,以及形成沙滩的范围k. 接下来n行,每行一个字符串。字符串的长度恰好是m,代表卫星照片的一行,其中 井号#表示一片水域; 半角点号.表示一片陆地
输出
输出一行一个整数,代表沙滩格子的数量
样例
输入
2 4 2 ##.# ...#
输出
26
输入
5 10 3 .........# ..######## .........# #....###.# ..####...#
输出
103
提示
对于40%的数据,满足n=m=1 对于100%的数据,满足1<=n,m<=100;1<=k<=10