19689번 - Collecting Mushrooms 다국어

Lim Li the Crab is running a mushroom plantation in her backyard. Her mushroom plantation can be modelled as a grid of R rows and C columns, and each grid square of her mushroom plantation can either be empty, contain a mushroom, or contain a sprinkler. For example, her mushroom plantation could look like this:

Figure 1: A mushroom farm with R = 5 and C = 5.

The distance between a sprinkler and a mushroom is defined as the maximum of their separation in the two axes. In other words, if the mushroom is located at row X_m and column Y_m while the sprinkler is located at row X_s and column Y_s, their distance will be max(|X_s − X_m|, |Y_s − Y_m|). Sprinklers only have a limited range, so a sprinkler can only water a mushroom if the distance between them is at most D. For example, if D = 1, the areas reachable by the two sprinklers will be:

Figure 2: Diagram showing the range of the sprinklers.

Mushrooms can only grow and be harvested if enough sprinklers are watering it. Specifically, a mushroom will be harvestable if at least K sprinklers are watering it. Count the number of harvestable mushrooms Lim Li can collect in her plantation.

The first line of input will contain four integers: R, the number of rows, C, the number of columns, D, the maximum distance between a sprinkler and a watered mushroom, and K, the minimum number of sprinklers required for a mushroom to be harvestable.

The next R lines of input will contain C characters each, containing a grid representing the mushroom plantation. Each character will represent the contents of a particular grid square, in the following way:

• ‘.’ represents an empty grid square,
• ‘M’ represents a grid square containing a mushroom,
• ‘S’ represents a grid square containing a sprinkler.

The output should contain one line with one integer, the maximum number of mushrooms Lim Li can harvest.

• 2 ≤ RC ≤ 500000,
• 1 ≤ D ≤ max(R, C),
• 1 ≤ K ≤ RC,
• there will be at least one mushroom,
• there will be at least one sprinkler.