[信息与未来 2022] 沙滩面积

Luogu

IDLGB3772

Time1000ms

Memory256MB

DifficultyP2

2022江苏信息与未来

我们获得了一幅陆地和水域情况的卫星照片，照片可以看成是一个 $n$ 行 $m$ 列的矩形，矩形中的每个格子要么是陆地（用半角点号 $\texttt{.}$ 表示），要么是水域（用井号 $\texttt{\#}$ 表示）。虽然卫星照片可以清楚的辨别出陆地和水域，但陆地的具体类型却并不明确。现在我们了解到，对于一块是水域的方格，它向上、下、左、右四个方向 $k$ 步之内可达的陆地格子，均会形成沙滩。例如，下图展示了 $k=2$ 的情况，蓝色的格子代表水域，标为黄色的陆地格子是沙滩。 ![](https://cdn.luogu.com.cn/upload/image_hosting/bermo74l.png) 你的任务是根据卫星照片计算出属于“沙滩”格子的数量。注意：卫星照片只拍摄了包含水域的部分，**水域附近的沙滩可能出现在卫星照片边界之外**。你可以假设卫星照片之外不存在任何水域。 ## Input 输入的第一行是空格分隔的三个整数 $n,m$ 和 $k$，代表拍摄的卫星照片共有 $n$ 行 $m$ 列，以及形成沙滩的范围 $k$。接下来 $n$ 行，每行一个字符串。字符串的长度恰好是 $m$，代表卫星照片的一行，其中： - 井号 $\texttt{\#}$ 表示一片水域； - 半角点号 $\texttt{.}$ 表示一片陆地。 ## Output 输出一行一个整数，代表沙滩格子的数量。 [samples] ## Note 对于 $40\%$ 的数据，满足 $n=m=1$；对于 $100\%$ 的数据，满足 $1\leq n,m\leq 100$，$1\leq k\leq 10$。

Samples

Input #1

2 4 2
##.#
...#

Output #1

Input #2

5 10 3
.........#
..########
.........#
#....###.#
..####...#

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[信息与未来 2022] 沙滩面积",
    "description": {
      "content": "我们获得了一幅陆地和水域情况的卫星照片，照片可以看成是一个 $n$ 行 $m$ 列的矩形，矩形中的每个格子要么是陆地（用半角点号 $\\texttt{.}$ 表示），要么是水域（用井号 $\\texttt{\\#}$ 表示）。 虽然卫星照片可以清楚的辨别出陆地和水域，但陆地的具体类型却并不明确。现在我们了解到，对于一块是水域的方格，它向上、下、左、右四个方向 $k$ 步之内可达的陆地格子，均会形成沙滩",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3772"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "我们获得了一幅陆地和水域情况的卫星照片，照片可以看成是一个 $n$ 行 $m$ 列的矩形，矩形中的每个格子要么是陆地（用半角点号 $\\texttt{.}$ 表示），要么是水域（用井号 $\\texttt{\\#}$ 表示）。\n\n虽然卫星照片可以清楚的辨别出陆地和水域，但陆地的具体类型却并不明确。现在我们了解到，对于一块是水域的方格，它向上、下、左、右四个方向 $k$ 步之内可达的陆地格子，均会形成沙滩...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments