AT_abc468_b.Corridor Watch

入门

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given integers M,DM,D and a string SS of length MM consisting of G and ..

There are MM cells arranged in a row from left to right, numbered 11 through MM from the left.

Some of the cells have a guardman standing on them. Specifically, a guardman stands on cell ii if Si=S_i= G, and no one stands on cell ii if Si=S_i= ..

A cell whose distance from a cell with a guardman is at most DD is watched by that guardman. That is, a cell xx is watched by a guardman if there exists a cell ii such that Si=S_i= G and ∣x−i∣≤D|x-i|\le D.

Among the MM cells, find the number of cells that are not watched.

给你整数 MM、DD 和一个长度为 MM 的字符串 SS,其中只包含字符 G 和 .。

从左到右依次排列着 MM 个格子,编号从左至右为 11 到 MM。

部分格子上站着守卫。具体而言:若 Si=S_i= G,则第 ii 个格子上站着一名守卫;若 Si=S_i= .,则第 ii 个格子上无人。

若某个格子与某守卫所在格子的距离不超过 DD,则该格子被该守卫监视。即:格子 xx 被某守卫监视,当且仅当存在某个格子 ii 满足 Si=S_i= G 且 ∣x−i∣≤D|x-i|\le D。

在全部 MM 个格子中,求未被监视的格子数量。

输入格式

The input is given from Standard Input in the following format:

MM DD
SS

输入从标准输入以如下格式给出:

MM DD
SS

输出格式

Output the answer.

输出答案。

输入输出样例

  • 输入#1

    7 1
    .G...GG

    输出#1

    1
  • 输入#2

    6 5
    ......

    输出#2

    6
  • 输入#3

    21 2
    ....G...GG.....G.....

    输出#3

    6

说明/提示

Sample 1 Explanation:
Only cell 44 is not watched.

Sample 2 Explanation:
All cells are not watched.

Constraints

  • 0≤D<M≤1000\le D < M \le 100
  • DD and MM are integers.
  • SiS_i is a string of length MM consisting of G and ..

样例 1 解释:
只有第 44 个格子未被监视。

样例 2 解释:
所有格子均未被监视。

约束条件

  • 0≤D<M≤1000\le D < M \le 100
  • DD 和 MM 均为整数。
  • SiS_i 是一个长度为 MM 的字符串,仅由字符 G 和 . 组成。

输入解题思路,AI测评打分。不知道怎么写?

首页